[数据结构与算法]LeetCode 45 跳跃游戏||

力扣

?思路：动态规划

定义dp数组? ?： dp[i]表示跳到下标为i的位置最少次数

初值? ? ? ? ? ? ??： dp[0]=0? ? （在第一个位置不需要跳）

状态转移方程：dp[i]=1+min{? dp[j]? },? ?当j-i<=nums[j]? , 1<i<=n,? 0<=j<i

? ? ? ? ? ? ??解释：如果跳到了第i个位置，那么可能是第0，1，...., i-1跳过去的

? ? ? ? ? ? ? ? ? ? ? ? 但是，如果前面的数不够大，就跳不过去。

? ? ? ? ? ? ? ? ? ? ? ? 所以，dp[i]=1+min{ dp[j] },? j为i之前的某个下标? 且? nums[j]? 足够大能跳到下标 i

? ? ? ? ? ? ? ? ? ? ? ??足够大：i-j<=nums[j]

代码

class Solution {
public:
    int jump(vector<int>& nums) {

vector<int>dp(nums.size(),1001);
dp[0]=0;
for(int i=1;i<nums.size();i++)
{
    for(int j=0;j<i;j++)
    {
        if(i-j<=nums[j])
        {
        dp[i]=min(dp[i],1+dp[j]);
        }
    }
}
return dp[nums.size()-1];
    }
};