递归函数 return 值而不分配额外的 space？

Question

所以我一直在尝试优化这个名为 Frog Jump 的 LeetCode 问题。以下是问题的基本描述：

Given a list of stones' positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.

If the frog's last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.

e.g: [0,1,3,5,6,8,12,17]

There are a total of 8 stones. The first stone at the 0th unit, second stone at the 1st unit, third stone at the 3rd unit, and so on... The last stone at the 17th unit.

Return true. The frog can jump to the last stone by jumping 1 unit to the 2nd stone, then 2 units to the 3rd stone, then 2 units to the 4th stone, then 3 units to the 6th stone, 4 units to the 7th stone, and 5 units to the 8th stone.

这是我的有效解决方案。我需要帮助的是如何在不分配额外的 res 数组的情况下输出相同的布尔值，该数组使用 DFS 存储所有探索路径的逻辑或。

class Solution:
    def canCross(self, stones: List[int]) -> bool:
        
        if stones[1] != 1:
            return False
        
        res = []
        memo = {}
        
        def dfs(curr_stone, last_stone, last_jump):
            
            if curr_stone == last_stone:
                res.append(True)
                return
            
            if curr_stone > last_stone:
                res.append(False)
                return
            
            for i in range(-1,2):
                next_stone = curr_stone + (last_jump + i)
                if next_stone in stones and next_stone > curr_stone and (next_stone, last_stone, last_jump+i) not in memo:
                    memo[(next_stone, last_stone, last_jump+i)] = 1
                    dfs(next_stone, last_stone, last_jump+i)
        
        dfs(1, stones[-1], 1)
        return any(res)

有人可以帮助我解决这些问题吗？我总是为这些问题苦苦挣扎，最终将值存储在一个数组中；但是，理想情况下，我希望递归代码的结果相同而不分配额外的 res 数组 space.

Answer 1

由于该函数的全部目的似乎可以归结为 return any(res)，因此您似乎应该 return True/False递归函数而不是追加它们，然后在找到单个 True 值后退出所有递归调用，而不用保存每个找到的值。

这将涉及检查从递归调用 dfs(next_stone, last_stone, last_jump+i) 中 return 编辑了什么，如果它是真的，只需 returning True:

from typing import List

class Solution:
    def canCross(self, stones: List[int]) -> bool:

        if stones[1] != 1:
            return False

        memo = {}

        def dfs(curr_stone, last_stone, last_jump):

            if curr_stone == last_stone:
                return True  # Return the results instead of appending them to a list

            if curr_stone > last_stone:
                return False

            for i in range(-1, 2):
                next_stone = curr_stone + (last_jump + i)
                if next_stone in stones and next_stone > curr_stone and (next_stone, last_stone, last_jump + i) not in memo:
                    memo[(next_stone, last_stone, last_jump + i)] = 1
                    rec_result = dfs(next_stone, last_stone, last_jump + i)
                    if rec_result:  # Then check the recursive results at the call-site
                        return True

        return dfs(1, stones[-1], 1)

我会注意到，我没有对此进行广泛的测试，但从一些快速的“头脑解释”来看，它似乎是等价的。

递归函数 return 值而不分配额外的 space？

Recursive function return value without allocating extra space?

python

recursion

depth-first-search