動機

我是看Solution才知道有人用DP

Problem

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

 

Example 1:

Input: nums = [2,3,1,1,4]Output: trueExplanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]Output: falseExplanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

 

Constraints:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 105

Sol

每次都是挑最大的間距的位置

class Solution:
    def canJump(self, ns: List[int]) -> bool:
        i = 0
        while i < len(ns)-1 and ns[i] > 0:
            #print(i)
            tmp = i
            for j in range(i+1,len(ns) if i+ns[i]+1 > len(ns) else i+ns[i]+1):
                #print(tmp,j)
                tmp = max(tmp,j,key=lambda x: x+ns[x])
            if i == tmp:
                i = i+ns[i]
            else:
                i = tmp
        return i >= len(ns)-1

Case study

從最後的index開始看能不能到目前的最後的index，如果能到，之後就是看後面的index能不能到這裡

這邊的重點是只要能到終點的點，就是終點

就像一個範圍越來越大一樣

public class Solution {
    public boolean canJump(int[] nums) {
        int lastPos = nums.length - 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (i + nums[i] >= lastPos) {
                lastPos = i;
            }
        }
        return lastPos == 0;
    }
}