世界500强公司面试题——台阶问题的分析与Python实现 原创 王帅
16lz
2021-03-24
问题描述:假设有一座高度是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;
方法一:使用递归算法,求解上面的问题.
运行结果:
方法二:使用动态规划来求解问题:
运行结果:
更多相关文章
- 2021-02-27:假设一个固定大小为W的窗口,依次划过arr,返回每一次滑出
- 深入理解Activity启动模式
- Android(安卓)bind其他或第三方APK Service方法
- android Activity之间跳转。
- 如何为不规则图形填充颜色 (注:图形是闭合的)
- 一起学android之自定义控件一起制作自定义标签(39)
- Android将String转化为ArrayList
- 查看android sqlite数据库常用操作
- Android(安卓)Intent 其中一个分析