萌新刷题之跳跃游戏

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。
示例 2:

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

class Solution {
    public boolean canJump(int[] nums) {
        int max = 0, i = 0;
        for (i = 0; i <= max && i < nums.length; i++) {
            max = Math.max(max, nums[i]+i);
        }
        return i == nums.length;
    }
}

class Solution:
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        maxpos = 0
        result = False
        for i in range(len(nums)-1):
            if maxpos<i:
                return False
            maxpos = max(maxpos,nums[i]+i)
        return True if maxpos >= len(nums)-1 else False

public class Solution {
    public boolean canJump(int[] A) {
        boolean[] can = new boolean[A.length];
        can[0] = true;

        for (int i = 1; i < A.length; i++) {
            for (int j = 0; j < i; j++) {
                if (can[j] && j + A[j] >= i) {
                    can[i] = true;
                    break;
                }
            }
        }

        return can[A.length - 1];
    }
}

class Solution:
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        n = len(nums)

        dp = [False] * n
        dp[-1] = True

        for i in range(n - 2, -1, -1):
            dp[i] = any(
                dp[i + j] if i + j < n else True
                for j in range(1, nums[i] + 1)
            )

        return dp[0]