贪心算法-01：跳跃游戏_代码007(未授权)

本文介绍: 贪心算法/跳跃游戏/力扣hot100

贪心算法是动态规划的一个特例，相对于动态规划，使用贪心算法需要满足更多条件，但是效率比动态规划要高。

贪心选择的性质就是：每一步都做出一个局部最优解，最终的结果就是全局最优。不过这是一种特殊性质，只有一部分问题拥有这个性质。

比如面前放有100张人民币，你只能拿十张。想要拿到最高的金额，就需要每次选择剩下钞票中面值最大的一张，最后你的选择一定是最优的。

使用动态规划解法就是 [分解问题]。

我们的原始问题是：从初始位置跳到最后一个位置的最小跳跃次数。

//定义dp函数：从索引p跳到数组末尾的最小跳跃次数为dp(nums,p)
int dp(int[] nums,int p)

if(p >= nums.length - 1){
    return 0;
}

public int jump(int[] nums) {
    int n = nums.length;
    //memo[i] 表示从 0 到 i 下标最少跳跃次数 
    int[] memo = new int[n];
    //将数组初始化为一个不可能取到的值，比如 n
    //(因为从 0 到 n-1 最多 n-1 步)
    Arrays.fill(memo, n);
    return dp(nums, 0, memo);
}

public int dp(int[] nums, int p, int[] memo) {
    int n = nums.length;
    //base case
    if (p >= n - 1) {
        return 0;
    }
    if (memo[p] != n) {
        return memo[p];
    }
    //获取索引 p 中的跳跃步数，做为选择列表
    int steps = nums[p];
    for (int i = 1; i <= steps; i++) {
        //写出子问题
        int subProblem = dp(nums, p + i, memo);
        //写出状态转移方程
        memo[p] = Math.min(memo[p], subProblem + 1);
    }
    return memo[p];
}

public int jump(int[] nums) {
    int n = nums.length;
    int end = 0, farthest = 0;
    int jumps = 0;
    for (int i = 0; i < n - 1; i++) {
        farthest = Math.max(nums[i] + i, farthest);
        //当下标遍历到我们目前能够到达的最远距离时，进行一次跳跃
        if (end == i) {
            jumps++;
            end = farthest;
        }
    }
    return jumps;
}

class Solution {
    public boolean canJump(int[] nums) {
        int farthest = 0;
        int n = nums.length;
        for(int i = 0;i < n - 1;i++){
            farthest = Math.max(farthest,i+nums[i]);
            if(farthest <= i){
                return false;
            }
        }
        return farthest >= n - 1;
    }
}