问题描述:假设有一座高度是30级台阶的楼梯,从下往上走,每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。
分析问题:
如果每次走一步,则需要走40步;
如果每次走两步,则需要走20步;
走一步和走两步可以有交叉,那么总共有多少种呢?
这时我们先假设台阶数为1,则方法只有一种,F(1) = 1;
假设台阶数为2,则可行的走法为(1,1)和(2) 共两种 F(2) =2;
假设台阶数为3,则可行的走法为(1,1,1),(2,1),(1,2) 共三种 F(3) = 3;
假设台阶数为4,则可行的走法为(1,1,1,1),(2,2)(2,1,1),(1,2,1),(111,2) 共五种,F(4)= 5;
假设台阶数为5,则可行的走法为(1,1,1,1,1)(1,2,2),(1,2,1,1),(1,1,2,1),(1,1,1,2),(2,2,1),(2,1,2),
(2,1,1,1) 共八种, F(5) = 8;
此时可以观察出来的规律为 F(5)= F(4) + F(3); F(4) = F(3)+F(2);同时可以罗列出当台阶数为6时,可行的走法为13种,F(6) = F(5) + F(4);
这样我们将一个复杂的问题,简化成了简单的问题,当台阶数为n时,此时有
F(n) = F(n-1) + F(n-2)(n>=3) ; F(1) =1 ; F(2) = 2;
方法一:使用递归算法,求解上面的问题.
运行结果:
方法二:使用动态规划来求解问题:
运行结果: