N阶台阶，假设每次走一步或两步，计算共有多少种走法。
以f（n）表示走N-n阶台阶有多少种方式
n表示目前剩余台阶数
首先计算最终状态（即走法少于2种的时候）：
最终状态为n=0，即到达终点记一种走法
当n=1时，走法只有f（n-1），所以也可直接返回1
中途每一台阶都有两种走法，所以有两个递归函数调用，以分支形式，最终每条分支到达终点都会增加1种走法返回，所以最先调用的函数会获得所有走法的记数
def up(n):
if n < 2:
return 1
else:
return up(n - 1) + up(n - 2)
# 两种等价
def up(n):
if n == 0:
return 1
if n == 1:
return up(n - 1)
# return 1 相等结果
else:
return up(n - 1) + up(n - 2) + up(n - 3)扩展一下，若每次可走三步或者以上（走法有三种），只需先计算最终状态，即走法少于三种的时候，分别为n=0，n=1，n=2，分别写好对应走法，中途都有三种，三条分支。
代码如下：
def up(n):
if n == 0:
return 1
elif n == 1:
return up(n - 1)
elif n == 2:
return up(n - 1) + up(n - 2)
else:
return up(n - 1) + up(n - 2) + up(n - 3)递推方式：（先求只走一步或两步的问题）
同样，先想最终状态，最后第N阶台阶，我们有多少种方式能够走上这一台阶？
对于最后一阶台阶，我们只有两种，即从n-2和n-1迈步过来，而且这两种对于已走过的步数而言，是必须走的，并没有增加种数,它仅等于走到前两步所拥有的种数而已。
（n-2阶台阶走一步到n-1台阶这一种方式其实已经记录在了n-1这一阶，所以说对于n-1，n-2来说，分别只有走一步和走两步各一种走法，并没有增加走台阶种数）
所以f(n)=f(n-1)+f(n-2)
而因为满足最优化结构，所以该方程可以递推到所有步数，除了前2步确定走到第n步有多少种方式（n<=2）
因此，我们发现，其实只需记录走到前两步的走法即可
def up2(n):
if n == 0:
return 0
elif n == 1:
return 1
elif n == 2:
return 2
else:
a = 1
b = 2
for i in range(2, n):
c = a + b
a = b
b = c
return c走三步：
同样，走到最终第N步，共有三个台阶可走到，即前三个台阶，而这三步对于前三个台阶而言，已是唯一走法，所以：
f(n)=f(n-1)+f(n-2)+f(n-3),可一直倒推到最前面3步，这3步是确定走这3步到底会有多少种，供后面递推时统计种数使用。
代码如下：
def up2(n):
if n == 0:
return 0
elif n == 1:
return 1
elif n == 2:
return 2
elif n == 3:
return 4
else:
a = 1
b = 2
c = 4
for i in range(3, n):
d = a + b + c
a = b
b = c
c = d
return d如果不明白为什么最终方程能够递推到前3步这一步骤，你可以先想象n=4，走到n=4这一步时，是不是只有从n=1，2，3这3个台阶走过来？（可走最多3步）
而走到n=1只有一种方式，
走到n=2只有两种方式
走到n=3只有四种方式，
而对于这三个台阶而言，走到n=4只有唯一一种
（n=1走到n=2，n=2走到n=3这种之类的已经被统计在n=2，n=3这些台阶的走法上了，所以唯一，没有再增加走法）
所以走到n=4满足方程，走到n=N亦满足方程，想推的话中间那些也一样，只要统计走到前三步的走法种数即可。