Jump Game II Leetcode，为什么我的记忆失败了？

Question

问题来了：

跳跃游戏II

给定一个非负整数数组

nums

，您最初位于数组的第一个索引处。

数组中的每个元素代表你此时的最大跳跃长度 位置。

你的目标是以最少的跳跃次数到达最后一个索引。

您可以假设您始终可以到达最后一个索引。

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

我的解决方案无需缓存即可工作。但是一旦我添加它，我就会得到错误的输入。

这是一个例子：

• 输入 =

  [1,2,1,1,1]

• 预期产出 =

  3

• 实际产量 =

  4

Answer 1

问题在于，在考虑所有替代方案之前，您就记住了从开始到当前索引的总步骤。找到第一条到达终点的路径后，我们知道这些距离可能还不是最佳的，但您仍然将它们存储在

memo

中。当您选择另一条路线到达同一点时，您相信

memo

可以为您提供最佳距离 - 这是一个错误的假设。

正确的记忆方法是存储前方的步数，就好像当前索引是起始点一样。由于仅在考虑了从该索引开始的所有替代方案时才存储该值，因此这是最佳值。

回溯时，在递归调用中添加 1 步。

这是采用该方法改编的代码：

    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]

Answer 2

TC = O(N) SC = O(1)

 int jump(vector<int>& nums) {
       int maxi = nums[0];
       int step = nums[0];
       int jumps = 1;
       if(nums.size() == 1) return 0;
       else if(nums[0] == 0) return -1;
       else {
              for(int i =1;i<nums.size();i++)
              {
                    if(i == nums.size() - 1)
                    {
                           return jumps;
                    }
                    maxi = max(maxi , i + nums[i]); //i is added because if zero or negative number comes in between and step goes to zero , we can't reach
                   step--;
                   if(step == 0) //need to take the jump
                   {
                       jumps++;
                       if(i >= maxi)
                       {
                              return -1;
                       }
                       step = maxi - i;
                   }
                }
              return -1; //if goes out of loop means can't reach
           }
   }