Jump Game II Leetcode, why is my memoization failing?

Here is the problem:

Jump Game II

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

class Solution:
    def jump(self, nums: List[int]) -> int:
        memo = {}
        result = self.helper(0, nums, 0, memo)
        return result
    def helper(self, numJump, nums, currentInd, memo):
        if currentInd in memo:
            return memo[currentInd]
        if currentInd == len(nums) - 1:
            return numJump
        val = nums[currentInd]
        totalMin = float("inf")
        for ind in range(1, val + 1):
            newInd = currentInd + ind
            if newInd >= len(nums):
                continue
            ret = self.helper(numJump + 1, nums, newInd, memo)
            if ret < totalMin:
                totalMin = ret
        if currentInd not in memo:
            memo[currentInd] = totalMin
        return totalMin

My solution works without my cache. But as soon as I add it, I get incorrect input.

Here is an example:

input = [1,2,1,1,1]
expected output = 3
actual output = 4

Solution

The problem is that you memoize the total steps from the beginning to the current index before all alternatives have been considered. After finding a first path to the end, we know that these distances might not be optimal yet, but still you store them in memo. As you then take an alternative route to get to the same point, you trust that memo to give you the optimal distance -- which is a wrong assumption.

The right way to memoize, is to store the number of steps ahead, as if the current index is the starting point. As this value is only stored when all alternatives starting at that index have been considered, this is an optimal value.

As you backtrack, add 1 step to what you get from the recursive call.

Here is your code adapted with that approach:

    def helper(self, nums, currentInd, memo):
        if currentInd in memo:
            return memo[currentInd]
        if currentInd == len(nums) - 1:
            return 0  # No more steps needed
        val = nums[currentInd]
        totalMin = float("inf")
        for ind in range(1, val + 1):
            newInd = currentInd + ind
            if newInd >= len(nums):
                break # No need to continue...
            ret = self.helper(nums, newInd, memo)
            if ret < totalMin:
                totalMin = ret
        memo[currentInd] = 1 + totalMin  # Add step taken
        return memo[currentInd]