Skip to main content

55. Jump Game

https://leetcode.com/problems/jump-game/

Python​

Bottom Up DP​

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        if len(nums) < 2:
            return True

        dp = [0] * (len(nums)-1)
        dp[0] = nums[0]

        for i in range(1, len(nums)-1):
            if dp[i-1] < i:
                return False
            dp[i] = max(dp[i-1], i+nums[i])

        return dp[-1] >= (len(nums)-1)

Top Down DP​

from functools import cache


class Solution:
    def canJump(self, nums: List[int]) -> bool:
        @cache
        def dp(i):
            if i >= len(nums)-1:
                return True

            for dest in range(i+1, i+nums[i]+1):
                reached = dp(dest)
                if reached:
                    return True
            return False

        return dp(0)

Javascript​

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {

    function recursive(idx, memo = {}) {
        if (memo.hasOwnProperty(idx)) return memo[idx];
        if (idx === nums.length - 1) return true;

        const steps = nums[idx];

        for (let step = 1; step <= steps; step++) {
            const nextStep = idx + step;

            if (recursive(nextStep, memo)) {
                memo[idx] = true;
                return true;
            }
        }

        memo[idx] = false;
        return false;
    }

    return recursive(0);
};