如何使这个贪心函数更快？

Question

我正在尝试解决一个问题，但我的代码在一个列表长度为 25000 的测试用例中失败了。有什么方法可以使它更快。我尝试使用 functools.lru_cache，但我仍然无法在要求的时间内完成运行。

这是网站的问题

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.

Determine if you are able to reach the last index.

这是我试过的

def can_jump(input_list):

    @lru_cache
    def helper(idx = 0):
        if idx == len(input_list) - 1:
            return True
        return any(helper(new_idx) for x in range(input_list[idx]) \
        if (new_idx := idx + x + 1) < len(input_list)) # increasing order of jumps

    return helper()

样本测试用例工作

input_list = [2,3,1,1,4]
print(can_jump(input_list)) # True
input_list = [3,2,1,0,4]
print(can_jump(input_list)) # False

我也试过从另一个方向走，

return any(helper(new_idx) for x in range(input_list[idx], 0, -1) \
if (new_idx := idx + x) < len(input_list)) # decreasing order of jumps

但是我仍然无法使这个运行足够快以清除25000个元素列表的最后一个测试用例，我在这里做错了什么？

Answer 1

好的，我想我明白了。你能试试这个吗？请注意，这直接取自：https://codereview.stackexchange.com/questions/223612/jump-game-leetcode

def canjump(nums):
    maximum_reachable_index = 0

    for index, max_jump in enumerate(nums):
        if index > maximum_reachable_index:
            return False

        maximum_reachable_index = max(index + max_jump, maximum_reachable_index)

    return True

如何使这个贪心函数更快？

How to make this greedy function faster?

python

time-complexity

greedy