【Check 77】2024-05-18 - 55. 跳跃游戏

[larscheng]

55. 跳跃游戏

[larscheng]

思路

动态规划1

• dp[i]表示能否跳跃到第i位，dp记录了能否跳跃的可能
• dp[i-1]=true,dp[i]=dp[i-1]&nums[i-1]>0
• dp[i-1]=false,dp[i-2]=true,dp[i]=dp[i-2]&num[i-2]>1 ...

  dp[i] = dp[i-1]&&nums[i-1]>0 || dp[i-2]&&nums[i-2]>1||...dp[0]&&dp[0]>i-0-1

• 时间复杂度：O(n*n)，空间复杂度：O(n)

动态规划2

• dp[i] 表示从[0,i]任意位置出发，最大可跳跃的位置

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

• dp[i] 超出最大位置，说明必然可跳跃到最大位置
• dp[i] = i，说明止步于此

• 复杂度更低 时间复杂度：O(n*n)，空间复杂度：O(n)

  代码

  
      public boolean canJump(int[] nums) {
          boolean[] dp = new boolean[nums.length];
          for (int i = 0; i <= nums[0] && i < nums.length; i++) {
              dp[i] = true;
          }
          for (int i = nums[0] + 1; i < nums.length; i++) {
              for (int j = i - 1; j >= 0; j--) {
                  dp[i] = dp[j] && nums[j] >= i - j;
                  if (dp[i]) {
                      break;
                  }
              }
          }
          return dp[nums.length-1];
      }
  }

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

[larscheng]

思路

记录每个节点可以跳到的最远位置 遍历的过程中如果当前位置大于历史最远位置，说明无法跳到该位置，否则说明可以跳完所有位置 O(n)/O(1)

代码

class Solution {

    public boolean canJump(int[] nums) {
        int k = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > k) {
                return false;
            }
            k = Math.max(k, i + nums[i]);
        }
        return true;
    }
}