戴维斯楼梯递归解法中memo位置对时间复杂度的影响疑问

记忆化缓存的核心作用是复用已经计算过的结果，两段代码的性能差异本质是memo字典的生命周期和共享范围不同：

• 将memo定义在函数内部的代码完全没有发挥缓存作用：每次调用stepPerms（包括递归调用自身的场景），都会重新初始化一个仅包含初始值的新memo字典，之前计算得到的所有n值结果都无法被后续调用复用。它的实际时间复杂度和无缓存的暴力递归完全一致，为*O(3ⁿ)*的指数级，n数值稍大就会触发超时。
• 将memo定义为全局变量的代码可以实现正常的记忆化效果：整个程序运行周期内仅存在一个memo字典，所有递归调用共享该缓存空间。每个n值只会被计算一次，计算完成后就会存入memo，后续需要用到该值时直接读取即可，时间复杂度降到*O(n)*的线性级别，完全可以满足题目时间限制要求。

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