#55 跳跃游戏(动态规划)

55. 跳跃游戏 - 力扣（LeetCode）

状态描述：dp[i]为i位置是否能到达

状态转移方程：dp[i] = (dp[i-1] && nums[i-1]>=1)|| (dp[i-2] && nums[i-2]>=2)||...|| (dp[i-n] && nums[i-n]>=n)

初态：dp[0]=1

class Solution {
public:
    bool canJump(vector<int>& nums) {
        vector<bool> dp(nums.size(),false);
        dp[0]=true;
        for(int i=1;i<nums.size();i++)
            for(int step=1;i-step>=0;step++)
                if(dp[i-step] && nums[i-step]>=step){
                    dp[i]=true;
                    break;
                }
        return dp[nums.size()-1];
    }
};