1- 问题描述
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
2- 思路分析
很自然的会想到递归，假设 n 级台阶有 T(n) 种不同走法。最后一步存在两种情况：剩下 1 级台阶，或者，剩下 2 级台阶。
第一种情形，则前面 n-1 步有 T(n-1)种走法；
第二种情形，则前面 n-2 步有 T(n-2)种走法。
故有：T(n) = T(n-1) + T(n-2)，其中 T(1) = 1, T(2) = 2。正好是 Fibonacci 数列！
递归算法能缩短程序代码、提高编程效率，但是它也有致命的弱点：如果递归调用地层次过多甚至无休止的进行递归调用，将耗尽系统资源（栈满），出现“堆栈溢出错误”。所幸的是，一般可以用递归解决的问题也可以用循环解决！
3- Python实现
# -*- coding: utf-8 -*-
# Climbing Stairs
# 递归实现 def climbStairs(n):
if not n: return 0
solv = []
solv.extend([1, 2]) # T(1), T(2)
if n >= 3:
for i in range(2, n):
solv.append(solv[i-1] + solv[i-2])
return solv[n-1]
# -*- coding: utf-8 -*-
# Climbing Stairs
# 循环实现 def climbStairs(n):
if not n: return 0
if n == 1: return 1
if n == 2: return 2 a, b = 1, 2
for i in range(2, n):
a, b = b, a + b
return b