1、前言

2、思路

1⃣️ 动态规划：
定义 dp[i] 表示到 i 位置的最小步骤。转移方程为：dp[i] = max {dp[i], dp[j] + 1}

2⃣️ 贪心：
贪心的思路跟跳跃游戏的思路差不多。

3、代码

动态规划：

public class Jump {

    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];

        for(int i = 0; i < n; i++){
            dp[i] = i;
        }

        for(int i = 1; i < n; i++){
            for(int j = 0; j <= i; j++){
                if(j + nums[j] >= i){
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }

        return dp[n - 1];
    }

    public static void main(String[] args) {
        System.out.println(new Jump().jump(new int[]{2,3,0,1,4}));
    }
}

贪心：

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int fastSteps = 0, end = 0, jumps = 0;
        for(int i = 0; i < n - 1; i++){
            fastSteps = Math.max(fastSteps, i + nums[i]);
            if(i == end){
                jumps++;
                end = fastSteps;
            }
        }

        return jumps;
    }
}