用while循环替换递归(爬楼梯难题):Python [英] Replacing recursion with while loop (stair climbing puzzle): Python

问题描述

我正在尝试用while循环替换递归，但是我陷入了以下问题.

I'm practicing replacing recursion with while loops, and I'm stuck on the following problem.

如果一次只能走1或2个楼梯，您可以用多少种方法爬上长度为n的楼梯?

How many ways can you go up a staircase of length n if you can only take the stairs 1 or 2 at a time?

递归解决方案非常简单:

The recursive solution is pretty simple:

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

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

I feel like the structure for the iterative program should go something like this:

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

但是我不知道我需要在#做某事中添加什么.有人能帮我吗?伪代码很好！

But I don't know what I need to put in the #do something part. Can someone help me? Pseudocode is fine!

推荐答案

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

This amounts to the top-down (recursive) approach vs. the bottom-up (iterative) approach for dynamic programming.

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

Since you know that for input n you need all values of stairs(p) for 0 <= p <= n. You can iteratively compute stairs(p) starting at p = 0 until you reach p = n, as follows:

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]

这篇关于用while循环替换递归(爬楼梯难题):Python的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！