[数据结构与算法]力扣hot100 55题跳跃游戏打卡

2021年11月22日

55. 跳跃游戏

给定一个非负整数数组?nums?，你最初位于数组的?第一个下标?。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。

?解题思路：从题目的要求来看做法应该是动态规划或者是贪心算法，此题两种算法均可解决。

方法一：贪心算法

用数组下标来记录位置的话，我们可以使用一个变量 rightMax 用来记录能够到达数组位置的最大值，通过for循环来不断的修改rightMax的值，一旦for循环中变量 i 走到的位置比目前的rightMax大，则循环结束，返回false。如果循环结束，没有问题，则返回true。

其中rightMax的更新方程为：Math.max(rightMax,i + nums[i])。

代码实现及提交结果如下图所示：

class Solution {
    public boolean canJump(int[] nums) {
        int len = nums.length;
        int rightmax = 0;
        for(int i = 0 ; i < len ; i++ ){
            if(i <= rightmax){
                rightmax = Math.max(rightmax,i + nums[i]);
            }else{
                return false;
            }
        }
        return true;
    }
}

方法二：动态规划

动态规划方法的大致思路就是定义一个dp数组用来存储每个位置还能够向前走的最大步数，状态转移方程为：dp[i] = Math.max(dp[i-1]-1,num[i])，但是此题因为只需要使用 dp[i-1] 是否等于 0 来判断是否还能接着往回走，所以仅仅使用一个变量来保存dp[i]的值即可。

2.1：正常使用dp数组来进行计算

设定一个dp数组，dp[i]表示在下标i处能够跳跃的最大值。
对于dp[i]，它等于dp[i-1]跳一格到达i处后剩余的步数，和nums[i]的最大值。因此得出状态转移方程为：dp[i]=max(dp[i-1]-1,nums[i])
边界条件：dp[0]=nums[0]
在每次循环开始，我们判断dp[i-1]是否等于0，若是，则不可能到达下标i处，dp[i] = 0;

代码和运行结果如下：

class Solution {
    public boolean canJump(int[] nums) {
        if(nums.length == 1){
            return true;
        }
        int len = nums.length;
        int dp[] = new int[len];
        dp[0] = nums[0];
        for(int i = 1 ; i < len ; i++ ){
            if(dp[i-1] > 0){
                dp[i] = Math.max(dp[i-1]-1,nums[i]);
            }else{
                dp[i] = 0;
            }
        }
        for(int i = 0 ; i < len ;i++){
            if(dp[i] == 0 && i != len-1){
                return false;
            }
        }
        return true;
    }
}

?2.1：使用常量来代替dp[i]进行计算
因为转移状态数组dp只和前一位有关，因此可以用滚动数组简化空间复杂度,并且每次之前进行检查 dp[i-1] 是否等于 0 ，如果等于，则说明根本到不了下一个坐标，直接返回false。

代码和结果如下：

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

?

总结：动态规划和贪心相比：贪心只是每一步都是最优，并且不考虑上一步的结果，但是动态规划的动态转移方程需要考虑到上一步甚至更上一步的状态。从两个方程便可明显的区别，贪心算法中，方程为：rightmax = Math.max(rightmax,i + nums[i]);很显然并没有用到上一步的结果。但是动态规划解题的状态转移方程当中，方程为：max = Math.max(dp[i-1]-1,num[i])，用到了上一步的最优结果。这也是区分贪心还是动态规划的一个地方。菜鸡，如有说错的地方，还望指出。