45. 跳跃游戏 II
给定一个长度为
n 的 0 索引整数数组 nums。初始位置为 nums[0]。每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
示例 1:
输入: nums = [2,3,1,1,4] 输出: 2
示例 2:
输入: nums = [2,3,0,1,4] 输出: 2
思路
动态规划步骤
1.确定数组的含义和数组存储的值 这里我们要求的是跳到n-1处所需的最小次数，那么dp数组的含义就是所有能够调到一个点的路径，dp[i]的含义是调到第i个点所需的最小次数，这样返回时，只需返回dp[n-1]即可
2.确定状态转移方程 如果要调到第i个点，那么从第一个点开始，到第i-1个点都是有可能调到第i个点的 拿样例来说， [2,3,1,1,4] 如果要跳到i=3处，那么可以从i=1处跳，也可以从i=2处跳，则dp[3] = min(dp[1]+1,dp[2]+1),所以我们需要从0到i-1遍历一遍，判断某个点是否能够调到i点 由此可以确定处状态转移方程， dp[i] = min(dp[i],dp[j]+1)
3.初始化 在i=0处，不需要跳，所以dp[0] = 0,另外还需要将数组其他的项初始化为无穷大 C++代码
代码
class Solution { public: int jump(vector<int>& nums) { int n = nums.size(); int dp[n]; memset(dp,0x3f,sizeof(dp)); dp[0] = 0; for(int i = 1;i < n;i++){ for(int j = 0;j < i;j++){ if (nums[j] + j >= i) { dp[i] = min(dp[i],dp[j]+1); } } } return dp[n-1]; } };