阶梯问题中的递归 W/Memoization 是自下而上的吗？

Question

将经典楼梯问题视为"Davis has a number of staircases in his house and he likes to climb each staircase 1, 2, or 3 steps at a time. Being a very precocious child, he wonders how many ways there are to reach the top of the staircase."

我的方法是使用递归的记忆作为

# 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 个值（想象一下递归树）。我认为这是自下而上的。这是正确的吗？

Answer 1

在top-down方法中，复杂模块被划分为子模块。所以这是自上而下的方法。另一方面，bottom-up 方法从基本模块开始，然后进一步组合它们。

此解决方案的自下而上方法是：

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]

Answer 2

递归策略通常是自上而下的方法，无论它们是否有记忆。底层算法设计是动态规划，传统上以 bottom-up 方式构建。

我注意到您在 python 中编写了您的代码，并且 python 通常对深度追溯不满意（少量是可以的，但性能很快就会受到影响并且有一个最大的追溯深度为 1000 - 除非自从我读到它后它被改变了）。

如果我们制作一个 bottom-up 动态程序版本，我们可以摆脱这种反应，我们也可以认识到我们只需要恒定数量的 space，因为我们只是真正感兴趣在最后 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]

请注意逻辑要简单得多，appart 从 i 开始比值小 1，因为位置从 0 而不是 1 的计数开始。

阶梯问题中的递归 W/Memoization 是自下而上的吗？

Is Recursion W/Memoization In Staircase Problem Bottom-Up?

algorithm

topdown

bottom-up