用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中.有人能帮我吗？伪代码很好!

Answer 1

这相当于自上而下(递归)方法与自下而上(迭代)方法进行动态编程.

既然你知道输入n你需要stairs(p)for的所有值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]