力扣Leetcode：45. 跳跃游戏 II（C++）
题目链接
https://leetcode-cn.com/problems/jump-game-ii/
题目描述
给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
思路
动态规划，dp[i]代表以到达数组i位置时的最少跳跃次数。
- 初始：dp[i]=0 if i==0 else ∞
- 状态转移：从位置i出发若能最多走j步，那么根据dp[i]的值可以更新dp[i+1] … dp[i+j]的值。
时间复杂度：若数组长度为N，数组元素平均大小为M，则时间复杂度为O(MN)。存在更优的解法，后续研究研究。
代码
class Solution {
public:
int jump(vector<int>& nums) {
int len=nums.size(),dp[len];
dp[0]=0;
for(int i=1; i<len; i++) {
dp[i]=99999;
}
for(int i=0; i<len; i++) {
for(int j=1; j<=nums[i] && i+j<len; j++) {
dp[i+j]=min(dp[i+j], dp[i]+1);
}
}
return dp[len-1];
}
};