递归中的跳跃博弈

Question

我试图测试自己理解递归的能力，所以我给自己一个任务，在递归中做跳跃游戏练习

给定一个非负整数数组，您最初位于数组的第一个索引处。数组中的每个元素代表该位置的最大跳转长度。你的目标是在最小的跳跃次数内达到最后一个指数。

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

我试图修改这部分代码，但它没有出现在调试器上，因此我没有真正看到这部分代码中的问题

def function(array, index, counter):
    if index >= len(array):
        return counter
    min_step = float('inf')
    for i in range(1, array[index]):
        min_step = min(min_step, function(array, index + i, counter + 1))

    return min(min_step, function(array[1:], index, counter))

如果有人能告诉我，我的想法是否正确

谢谢你：）

Answer 1

你的功能很好，只是几个修复：

1. 你想得到最后一个索引，它是len（数组）-1，而不是len（数组）。
2. 要启用跳转到当前数组值的距离，因此需要范围（1，数组[index] 1）而不是范围（1，数组[index]）。
3. min_step已经包含最少的跳跃量。我不知道你想返回什么，但是你可以返回min_step。

考虑到这一点：

def function(array, index, counter):
    if index >= len(array) - 1:
        return counter
    min_step = float('inf')
    for i in range(1, array[index] + 1):
        min_step = min(min_step, function(array, index + i, counter + 1))

    return min_step