LeetCode--跳跃游戏(动态规划贪心算法)

跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]

输出: true

解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4]

输出: false

解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ，所以你永远不可能到达最后一个位置。

动态规划解法一：

状态变量

dp[i] 表示是否可以到达位置i

转移方程

dp[i] = (dp[j] == true && nums[j] >= (i-j)) (j >=0 to j<i) ? dp[i] = true :dp[i] = false;

初始值

dp[0] = true;

动态规划解法二：

状态变量

dp[i] 表示从前面跳到i以后的剩余步数

转移方程

dp[i] =max(dp[i -1],nums[i-1] -1);

初始值

dp[0] = 0;

解法一动态规划

这个题我们可以从后往前分析，首先判断倒数第二个元素能否到达最后一个元素，如果可以，我们将不再考虑最后一个元素，

因为根据刚才的分析如果可以到达倒数第二个，那么也可以到达最后一个元素。

/**
 * @Author liuhaidong
 * @Description 动态规划1
 * @param
 * @Date 20:02 2019/10/6 0006
 */
public static boolean canJump(int[] nums) {
    if(nums == null){
        return false;
    }
    boolean[] dp = new boolean[nums.length];
    dp[0] = true;
    for(int i =1;i<nums.length;i++){
        for(int j =0;j < i;j++){
            // 如果之前的j节点可达，并且从此节点可以到跳到i
            if(dp[j] == true && nums[j] +j >=i){
                dp[i] = true;
                break;
            }
        }
    }
    return dp[nums.length - 1];
}

动态规划2

/**
 * @Author liuhaidong
 * @Description 动态规划2
 * @param
 * @Date 20:02 2019/10/6 0006
 */
public static boolean canJump1(int[] nums) {
    int[] dp = new int[nums.length];
    dp[0] = 0;
    for(int i =1;i<nums.length;i++){
        dp[i] = Math.max(dp[i-1],nums[i-1])-1;
        if(dp[i] < 0){
            return false;
        }
    }
    return dp[nums.length-1] >=0;
}

贪心

我们记录一个的坐标代表当前可达的最后节点，这个坐标初始等于nums.length-1，
然后我们每判断完是否可达，都向前移动这个坐标，直到遍历结束。

如果这个坐标等于0，那么认为可达，否则不可达。

class Solution {
    public boolean canJump(int[] nums) {
        
        if (nums == null) {
            return false;
        }
        int lastPosition = nums.length - 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            // 逐步向前递推
            if (nums[i] + i >= lastPosition) {
                lastPosition = i;
            }
        }
        return lastPosition == 0;
    }
}

这段代码的时间复杂度是O(n)，空间复杂度是O(1)，可以看出比动态规划解法有了明显的性能提升。