python - 用 while 循环替换递归(爬楼梯拼图): Python

Question

我正在练习用 while 循环替换递归，但我遇到了以下问题。

如果你一次只能走 1 或 2 段楼梯，你有多少种方式可以走上长度为 n 的楼梯？

递归解决方案非常简单:

def stairs(n):
  if n <= 1:
    return 1
  else:
    return stairs(n-2) + stairs(n-1)

我觉得迭代程序的结构应该是这样的:

def stairs_iterative(n):
  ways = 0
  while n > 1:
    # do something
    ways +=1
  return ways

但我不知道我需要在#do something 部分添加什么。有人能帮我吗？伪代码很好!

Answer 1

这相当于动态规划的自上而下(递归)方法与自下而上(迭代)方法。

因为您知道输入 n您需要 stairs(p) 的所有值对于 0 <= p <= n .您可以迭代计算 stairs(p)从 p = 0 开始直到你到达 p = n ，如下:

def stairs(n):
    table = [1, 1]  # p = 0 and p = 1
    for i in range(2, n + 1):
        table.append(table[i - 2] + table[i - 1])
    return table[n]