algorithm - 递归使用/存储在楼梯问题中是自下而上的吗？

把经典的楼梯问题看作“戴维斯家里有很多楼梯，他喜欢一次爬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个值（想象递归树）。我认为这是自下而上的这是对的吗？

最佳答案

不管他们是否有记忆，复述策略通常都是自上而下的方法。底层算法设计是动态规划，传统上是自下而上的。
我注意到你在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的appart比值小一，因为位置是从0开始的，而不是从1开始的。