爬楼梯Top-down记忆化搜索返回逻辑疑问及代码优化咨询

两处return memo[n]的作用 #

记忆化递归的核心逻辑是已经计算过的结果直接读缓存，不要重复计算，你修改后的版本逻辑是错误的：

• 第一处return memo[n]的触发条件是memo.get(n)为真，也就是n对应的走法数已经计算过并存进了缓存字典，这时候直接返回缓存值即可，不需要再走递归计算逻辑，这一步是减少重复计算的关键。
• 第二处return memo[n]是当n的结果没有缓存过，第一次计算完成后，把结果存到缓存再返回，供后续调用读取。

你修改后的版本会跳过「缓存命中直接返回」的逻辑，不管有没有算过n的结果，都会重新执行一遍递归计算，memo缓存完全没有起到作用，时间复杂度和无记忆化的暴力递归一样是O(2^n)，n稍大就会超时。

现有代码注释的错误 #

你写的注释有几处明显和代码逻辑不符：

• #Return None：对应代码返回的是0，不是None，n<0代表走法非法，返回0是正确逻辑，注释描述错误。
• #There is an error while executing the program and it is not performing what it was intended to do：对应代码是n==0的情况，代表刚好走完所有台阶，是1种合法走法，返回1是正确设计，和程序报错没有任何关系，注释描述完全错误。
• 其他注释表述比较啰嗦，但逻辑没有本质错误，建议简化为对应代码的实际作用即可，比如memo的作用是「缓存已计算的n对应的走法数，减少重复递归」。

更优化的实现方式 #

这个问题本质是斐波那契数列的应用，走法数满足f(n) = f(n-1) + f(n-2)，初始条件f(0)=1, f(1)=1。最高效的入门级实现是迭代版动态规划，既没有递归的栈溢出风险，还能把空间复杂度优化到O(1)：

class Solution:
    def climbStairs(self, n: int) -> int:
        # 边界情况直接返回
        if n <= 1:
            return 1
        # 只保存前两个状态的值，不需要存整个dp数组
        pre2 = 1 # 对应f(n-2)，初始为f(0)
        pre1 = 1 # 对应f(n-1)，初始为f(1)
        for _ in range(2, n+1):
            current = pre1 + pre2
            # 状态前移
            pre2, pre1 = pre1, current
        return pre1

这个实现的时间复杂度是O(n)，空间复杂度是O(1)，比递归记忆化版本的性能更高，也不会出现递归深度过大的栈溢出问题。

内容的提问来源于stack exchange，提问作者jkjhrmv