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.

For example:

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

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

先尝试DFS,大数据的时候果然TLE.仔细看，中间有大量的重复的步骤，比如：[2]这个节点可能的情况是step = 1 or step = 2，这种情况在

3先step = 1到2之后，又进行了一次.复杂度很大，都和取值有关系

dp[i]表示从0到i是否可达到:dp[i] = {dp[0]..dp[j]..dp[i-1] if dp[j] && A[j] >= i-j} dp[0] = true others dp[i] = false;

class Solution {
public:
    bool canJump(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<bool> dp(n,false);
        dp[0] = true;
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                if (dp[j] && A[j] >= i - j){
                    dp[i] = true;
                    break;
                }
            }
            //可以提前退出
            if (!dp[i]){
                return false;
            }
        }
        return dp[n-1];
    }
};

原文链接: https://www.cnblogs.com/kwill/p/3188016.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍