Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

lintcode

Example

A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

Sulotuons

Solution 1: Dynamic Programming

• state: f[i] -- 从0可以调到i.
• function：f[i] = 在i之前存在j满足可以从0跳到j并且可以从j调到i
• initialization: f[0] = true;
• final answer: f[n-1]
• 时间复杂度$$O(n^2)$$，空间复杂度$$O(n)$$

class Solution {
public:
    /**
     * @param A: A list of integers
     * @return: The boolean answer
     */
    bool canJump(vector<int> A) {
        // write you code here
        int n = A.size();
        vector<bool> iJump(n, false);
        iJump[0] = true;
        for(int i=1; i<n; i++) {
            for(int j=0; j<i; j++) {
                if(iJump[j] && j+A[j]>=i) {
                    iJump[i] = true;
                    break;
                }
            }
            if(f[i] == false) { //没有这个判断的话会超时。i都到达不了就不用往后看了。
                return false;
            }
        }
        return iJump[n-1];
    }
};

Solution 2: Dynamic Programming

• 换一种状态，f[i]表示从0到i还剩余的最大步数
• function: f[i] = max(f[i-1], A[i-1]) - 1
• 时间复杂度O(n)，空间复杂度O(n)

class Solution {
public:
    /**
     * @param A: A list of integers
     * @return: The boolean answer
     */
    bool canJump(vector<int> A) {
        // write you code here
        int n = A.size();
        vector<int> f(n, 0);
        f[0] = 0;
        for (int i=1; i<n; i++) {
            f[i] = max(f[i-1], A[i-1]) -1;
            if(f[i] <0) {
                return false;
            }
        }
        return f[n-1]>=0;
    }
};

因为第i个状态只跟它的前一个状态有关系，这样的话完全没有必要用数组存所有状态了啊，只要用一个变量存储前一个状态就可以了。空间复杂度降为$$O(1)$$.

bool canJump(vector<int> A) {
        if(A.empty()) return false;
        int n = A.size();
        int step_left = 0;
        for(int i=1; i<n; i++) {
            step_left = max(A[i-1], step_left) - 1;
            if(step_left < 0) return false;
        }
        return step_left >=0;
    }

Solution 3: 贪心法(greedy algorithm)

• 贪心选择性质(greedy-choice property)

• 最优子结构(optimal substructure)

  有上述两个性质的问题可以用贪心法来解（需要总结。。。）

• 一阶一阶上，看能不能上到最高（n-1)

class Solution {
public:
    /**
     * @param A: A list of integers
     * @return: The boolean answer
     */
    bool canJump(vector<int> A) {
        // write you code here
        int n = A.size();
        int r = 0;//most right position
        for(int i=0; r>=i && r<n; i++) {
            r = max(A[i]+i, r); //update r
        }
        return r>=n-1;
    }
};

一个更容易理解的写法

bool canJump(vector<int> A) {
        // write you code here
        int mostRight = 0;
        int n = A.size();
        for(int i=0; i<A.size(); i++) {
            if(mostRight < i) return false;
            if(i+A[i] > mostRight) {
                mostRight = i+A[i];
            }
            if(mostRight>=n-1) break;
        }
        return true;
    }

• 类似的，也可以一阶一阶下，看能不能下到最低（0）