阶梯问题中的递归和记忆是自下而上的吗？
阶梯问题中的递归和记忆是自下而上的吗？
提问于 2019-06-23 14:07:27
考虑到经典的楼梯问题，“戴维斯的房子里有许多楼梯，他喜欢一次爬1级、2级或3级楼梯。作为一个非常早熟的孩子，他想知道有多少方法可以到达楼梯的顶部。”
我的方法是使用内存化和递归，如下所示
# TimeO(N), SpaceO(N), DP Bottom Up + Memoization
def stepPerms(n, memo = {}):
if n < 3:
return n
elif n == 3:
return 4
if n in memo:
return memo[n]
else:
memo[n] = stepPerms(n - 1, memo) + stepPerms(n - 2 ,memo) + stepPerms(n - 3 ,memo)
return memo[n]我想到的问题是，这个解决方案是自下而上还是自上而下。我的方法是，因为我们一直往下计算上N个值(想象一下递归树)。我认为这是自下而上的。这是正确的吗？
回答 2
Stack Overflow用户
回答已采纳
发布于 2019-06-23 15:21:15
递归策略通常是自上而下的方法，无论它们是否有内存。底层算法设计是动态编程，传统上是以自下而上的方式构建的。
我注意到你的代码是用python编写的，而python通常对深度递归并不满意(少量是可以的，但性能很快就会受到影响，最大的递归深度是1000 -除非我读到它之后发生了变化)。
如果我们做一个自下而上的动态编程版本，我们可以摆脱这种递归，我们也可以认识到我们只需要恒定的空间量，因为我们只对最后3个值感兴趣：
def stepPerms(n):
if n < 1: return n
memo = [1,2,4]
if n <= 3: return memo[n-1]
for i in range(3,n):
memo[i % 3] = sum(memo)
return memo[n-1]请注意，逻辑要简单得多，因为从i开始的位置是从0开始的，而不是计数1。
Stack Overflow用户
发布于 2019-06-23 15:03:50
在自上而下的方法中，复杂的模块被划分为子模块。所以这是一种自上而下的方法。另一方面，自下而上的方法从基本模块开始，然后进一步组合它们。
此解决方案的自下而上方法将是：
memo{}
for i in range(0,3):
memo[i]=i
memo[3]=4
for i in range(4,n+1):
memo[i]=memo[i-1]+memo[i-2]+memo[i-3]页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/56724665
复制相关文章
点击加载更多
相似问题
bluetoothLeScanner扫描时间有多长？
从扫描请求/扫描应答包获取RSSI
android系统的连续RSSI扫描
由阿尔特信标库127返回的rssi扰乱了距离
BluetoothLeScanner开始扫描仅转到错误代码2
添加站长 进交流群
领取专属 10元无门槛券
AI混元助手 在线答疑
关注 腾讯云开发者公众号
洞察 腾讯核心技术
剖析业界实践案例
腾讯云开发者
