python算法：如何解决楼梯台阶问题-mile米乐体育
本文由码农网 – 小峰原创翻译，转载请看清文末的转载要求，欢迎参与我们的付费投稿计划！
让我们考虑以下问题。
有一个有n个台阶的楼梯，你一次可以爬1或2个台阶。
给定n，编写一个函数，返回爬完楼梯的方式数量。步骤的顺序很重要。
例如，如果n是4，那么有5种方式：
- 1,1,1,1
- 2,1,1
- 1,2,1
- 1,1,2
- 2,2
如果规定的不是一次只能爬1或2步，而是可以使用正整数x集合内的任意数字爬楼梯，那会怎么样？例如，如果x = {1,3,5}，则表示一次爬升1，3或5阶楼梯。
mile米乐体育的解决方案
从一些测试案例开始总是好的做法。让我们从小的案例开始，看看能否找到某种规律。
- n = 1，1种爬楼方式：[1]
- n = 2，2种爬楼方式：[1,1]，[2]
- n = 3，3种爬楼方式：[1,2]，[1,1,1]，[2,1]
- n = 4，5种爬楼方式：[1,1,2]，[2,2]，[1,2,1]，[1,1,1,1]，[2,1,1]
你有没有注意到什么？请看n = 3时，爬完3阶楼梯的方法数量是3，基于n = 1和n = 2。存在什么关系？
爬完n = 3的两种方法是首先达到n = 1，然后再往上爬2步，或达到n = 2再向上爬1步。所以 f(3) = f(2) f(1)。
这对n = 4是否成立呢？是的，这也是成立的。因为我们只能在达到第三个台阶然后再爬一步，或者在到了第二个台阶之后再爬两步这两种方式爬完4个台阶。所以f(4) = f(3) f(2)。
所以关系如下： f(n) = f(n – 1) f(n – 2)，且f(1) = 1和f(2) = 2。这就是斐波那契数列。
def fibonacci(n): if n <= 1: return 1 return fibonacci(n - 1) fibonacci(n - 2)
当然，这很慢（o(2^n)）——我们要做很多重复的计算！通过迭代计算，我们可以更快：
def fibonacci(n): a, b = 1, 2 for _ in range(n - 1): a, b = b, a b return a
现在，让我们尝试概括我们学到的东西，看看是否可以应用到从集合x中取步数这个要求下的爬楼梯。类似的推理告诉我们，如果x = {1,3,5}，那么我们的算法应该是f(n) = f(n – 1) f(n – 3) f(n – 5)。如果n <0，那么我们应该返回0，因为我们不能爬负数。
def staircase(n, x): if n < 0: return 0 elif n == 0: return 1 elif n in x: return 1 sum(staircase(n - x, x) for x in x if x < n) else: return sum(staircase(n - x, x) for x in x if x < n)
这也很慢（o(|x|^n)），因为也重复计算了。我们可以使用动态编程来加快速度。
每次的输入cache[i]将包含我们可以用集合x到达台阶i的方法的数量。然后，我们将使用与之前相同的递归从零开始构建数组：
def staircase(n, x): cache = [0 for _ in range(n 1)] cache[0] = 1 for i in range(n 1): cache[i] = sum(cache[i - x] for x in x if i - x > 0) cache[i] = 1 if i in x else 0 return cache[-1]
现在时间复杂度为o(n * |x|)，空间复杂度为o(n)。
欢迎继续探索其他有趣的编程问题。
译文链接：http://www.codeceo.com/article/python-staircase-problem.html 英文原文：how to solve the staircase problem 翻译作者：码农网 – 小峰 [ 转载必须在正文中标注并保留原文链接、译文链接和译者等信息。]