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 1
elif sum <0:
return 0
return 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,4
while sum-1>0:
a,b,c = b,c,a+b+c
sum -= 1
return a
python爬楼梯多少种_Python 爬楼梯问题--有n阶台阶 上楼可以一步上1阶 2阶 3阶 计算共有多少种不同的走法？...
