【算法分析与设计】跳跃游戏

题目

给定一个长度为?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。
?    从下标为 0 跳到下标为 1 的位置，跳?1?步，然后跳?3?步到达数组的最后一个位置。

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

思想（动态规划）

????????动态规划，无非就是利用历史记录，来避免我们的重复计算。而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存。下面我们先来讲下做动态规划题很重要的三个步骤，

????????第一步骤：定义数组元素的含义，上面说了，我们会用一个数组，来保存历史数组，假设用一维数组 dp[] 吧。这个时候有一个非常非常重要的点，就是规定你这个数组元素的含义，例如你的 dp[i] 是代表什么意思？

????????第二步骤：找出数组元素之间的关系式，我觉得动态规划，还是有一点类似于我们高中学习时的归纳法的，当我们要计算 dp[n] 时，是可以利用 dp[n-1]，dp[n-2]…..dp[1]，来推出 dp[n] 的，也就是可以利用历史数据来推出新的元素值，所以我们要找出数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，这个就是他们的关系式了。而这一步，也是最难的一步，后面我会讲几种类型的题来说。

????????第三步骤：找出初始值。学过数学归纳法的都知道，虽然我们知道了数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，我们可以通过 dp[n-1] 和 dp[n-2] 来计算 dp[n]，但是，我们得知道初始值啊，例如一直推下去的话，会由 dp[3] = dp[2] + dp[1]。而 dp[2] 和 dp[1] 是不能再分解的了，所以我们必须要能够直接获得 dp[2] 和 dp[1] 的值，而这，就是所谓的初始值。

????????由了初始值，并且有了数组元素之间的关系式，那么我们就可以得到 dp[n] 的值了，而 dp[n] 的含义是由你来定义的，你想求什么，就定义它是什么，这样，这道题也就解出来了。

算法分析与设计

状态定义
dp[i]为跳跃到第i个元素时最小的跳跃数。
转移方程
我们对于当前i，应该是由[0,i-1]的元素跳到i来的，假设0<=j<i$$j+nums[j]>i,那么可以从dp[j]+1转移到dp[i]，所以我们要在所有的这种情况中选最小的
dp[i]=min(dp[i],dp[j]+1 if j+nums[j]>i);
初始化
如果当前只有1个元素，那么认为已经到达了，dp[0]=0

这是样例里的，只有一个元素时，最小跳跃次数为0

dp数组默认要求最小，所以初始化为最大值
注意
这里把dp[0]认为有一个元素，当然也可以是dp[1]认为是一个元素。只不过对应边界要改

代码实现

class Solution {
    public int jump(int[] nums) {
        int n=nums.length;
        int[] dp=new int[n];
        dp[0]=0;
        for(int i=1;i<n;i++){
            dp[i]=n;
        }
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[j]+j>=i){
                    dp[i]=Math.min(dp[j]+1,dp[i]);
                }
            }
        }
    
    return dp[n-1];
    }
}

运行结果