#45 跳跃游戏 II(动态规划)

45. 跳跃游戏 II - 力扣（LeetCode）

状态描述：dp[i]为到达i需要的最短跳数。

状态转移：dp[i]=min(dp[i-1]+1,dp[i-2]+1,....,dp[i-n]+1)

初态：dp[0]=0

使用大数表示不可达简化代码

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