假设你需要走n 阶楼梯才能到达楼顶,走楼梯的方式有两种,一次走1个台阶或者一次走2个台阶,问有多少种不同的方法可以走完这n阶楼梯?...先穷举几个n值分析下:
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=5,共8种
{1,2,2},{1,1,1,2},{2,1,2},
{1,1,2,1},{2,2,1},{1,2,1,1},{1,1,1,1,1},{2,1,1,1...}
可以看到,除了n=1和n=2两种情况,是固定的走法外;
走n阶台阶时,可以在n-2个台阶的基础上一次走2个台阶,也可以在n-1个台阶的基础上走1个台阶;也就是f(n)=f(n-1)+f(n-2),这个公式就是著名的斐波那契数列...,却不是算法上最优的.明显在计算n时,会计算两次n-2,时间复杂度是O(n^n),效率相当低的算法了.