Python爬楼梯问题：有n阶台阶，上楼可以一步上1阶,2阶，3阶，计算共有多少种不同的走法？
总共n步台阶（先假设n>3），f(n)表示n步台阶的走法总数
1、第一步如果是只走1步台阶，剩下的n-1步台阶怎么走（多少种走法）就只和n-1步台阶有关，f(n-1)
2、第一步如果是走2步台阶，剩下的n-2步台阶怎么走（多少种走法）就只和n-2步台阶有关，f(n-2)
3、第一步如果是只走3步，剩下的n-3步台阶怎么走（多少种走法）就只和n-3步台阶有关，f(n-3)
高中数学的排列：迈开步子的第一步有3种走法，再去算1、2、3种走法的总数加起来就是总的走法数。
第一步走1阶台阶，2阶台阶，3阶台阶，各是一种走法，1、2、3加起来就是走法的总数了
fn(n)=fn(n-1)+fn(n-2)+f(n-3) # 这种款式的表达式是不是类似斐波那契数列？
（斐波那契数列定义：0、1、1、2、3、5、8.。。。f(n)=f(n-1)+f(n-2）
假设总共3步台阶：1、1、1， 2、1， 3， 1、2总共四种走法
1-1-1
1-2
2-1
3
1、第一步走1步，走完所有台阶的走法，只与剩下的2步台阶有多少种走法有关了，fn(3)=fn(2)，总共2中走法
2、第一步走2步，走完所有台阶的走法，只与剩下的1步台阶有多少种走法有关了，fn(3)=fn(1)，总共1中走法
3、第一步走3步，走完所有台阶的走法，只与剩下的0步台阶有多少种走法有关了，fn(3)=fn(0)，总共1种走法 。这里不要纠结fn(0)=1
fn(3)=2+1+1=4
所以这个等式成立不啊？！
fn(3)=fn(3-1)+fn(3-2)+f(3-3)
==>fn(3) = fn(2)+fn(1)+f(0)
==>fn(3) = fn(1)+fn(0)+fn(1)+fn(0)
这么理顺下来，就是归并排序用到的分而治之的思想，分到最细，1步阶梯只有1种走法，但因为递归运算要设置条件fn(0)=1,才能递归算下去
from functools import lru_cache #python函数工具包里的缓存模块@lru_cache(1024)def sum_stairs_recursion(sum):"""有n阶台阶，上楼可以一步上1阶,2阶，3阶，计算共有多少种不同的走法？递归算法不加缓存模块sum>100,一般电脑就很难算出来了，试了下n=30，i5四核跑了50秒:param sum:传入楼梯数 int :return: int """if sum==0:return 1elif sum <0:return 0return sum_stairs_recursion(sum-1)+sum_stairs_recursion(sum-2)+sum_stairs_recursion(sum-3)def sum_stairs_Fibo(sum):"""非递归算法，斐波那契数列台阶数：1、2、3、4、5、6走法数：1、2、4、7、13、24:param sum::return:"""a,b,c = 1,2,4while sum-1>0:a,b,c = b,c,a+b+csum -= 1return a
