LeetCode 55. Jump Game

This post was migrated from Tistory. You can find the original here.

Problem

https://leetcode.com/problems/jump-game/description/?source=submission-noac

Approach

My first instinct was DP.

If $ A_{n-1}, A_{n-4}, A_{n-7} …. $ can all jump to $ A_{n} $,

then I’d keep looking for which elements $ A_{n-4}, A_{n-6}, A_{n-7} …. $ can jump to $ A_{n-1} $, and so on,

updating dp to True if I could eventually reach $ A_{0} $, and False if I couldn’t.

So the idea was: run the logic for every case that reaches $ A_{n} $, and if a value was already in the DP table, treat it as a shortcut since it had already been computed from some other case.

But it turns out DP wasn’t necessary at all.

Any element that can jump to $ A_{n-1} $ also belongs to the set of elements that can jump to $ A_{n} $. For example, an $ A_{n-4} $ that can reach $ A_{n} $ cannot possibly fail to reach $ A_{n-1} $.

In other words, instead of running the logic for every case that reaches $ A_{n} $, you can just walk backward from $ A_{n} $ and simply update the target element as you go.

The original approach wasn’t drastically slow either, since the DP gave it a shortcut, but it did extra unnecessary work, so it ends up slower than the version without DP. And the version without DP is much cleaner.

Also, if you write this recursively, you end up spending a lot of time chasing down edge cases you missed.

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        target = len(nums) - 1
        for i in range(len(nums)-2, -1, -1):
            distance = target - i
            if nums[i] >= distance:
                target = i
        return True if target == 0 else False

# Logic with DP

class Solution:
    dp = []
    def logic(self, nums, target):
        if target == 0:
            return True
        for i in range(target-1, -1, -1):
            distance = target - i
            if nums[i] >= distance:
                if self.dp[i] == True:
                    return True
                elif self.dp[i] == False:
                    continue

                if self.logic(nums, i):
                    self.dp[i] = True
                    return True
                else:
                    self.dp[i] = False
        return False

    def canJump(self, nums: List[int]) -> bool:
        leng = len(nums)
        self.dp = [ "x" for i in range(leng) ]
        return self.logic(nums, leng-1)