欢迎点击「算法与编程之美」↑关注我们!
本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列文章。
问题描述
一个楼梯有20级,每次可以爬1级或2级,请问从底到顶一共有多少种方法?
解决方案
步骤1:用函数的形式来表示题目结果。
设f(x)=y,表示一个有x级的楼梯,从底到顶爬上去一共有y种方法。
本题要求的便是f(20)的结果,即有20级楼梯一共有多少中方法。
步骤2:分析递推情况。
平时大家都喜欢爬楼梯,有时喜欢一次爬一级楼梯,有时喜欢一次爬两级楼梯。接下来考虑当你开始迈出第一步的情况。
你迈出的第一步可能是一级楼梯,也可能是两级楼梯。
如果迈出的是一级楼梯,那么接下来还有(20-1) = 19级楼梯要爬,19级楼梯的爬楼有f(19)种方法。
如果迈出的是二级楼梯,那么接下来还有(20-2) = 18级楼梯要爬,18级楼梯的爬楼有f(18)种方法。
因此爬20级楼梯一共有多少种方法,就取决于爬19级楼梯和爬18级楼梯一共有多少种方法,即f(20) = f(19) + f(18)。
以此类推,
f(19) = f(18) + f(17)
f(18) = f(17) + f(16)
...
f(2) = 2 # 爬二级楼梯有两种方法,分别是一次二级和两次一级
f(1) = 1 # 爬一级楼梯只有1种方法
步骤3:算法实现。
接下来将介绍python的实现代码如下:
import numpy as np MAX_STEP = 20 dp = np.zeros((MAX_STEP,), dtype=np.int) dp[1] = 1 dp[2] = 2 for i in range(3, MAX_STEP): dp[i] = dp[i-1] + dp[i-2] print(dp) |
---|
结语
本文给大家介绍了利用动态规划算法求解爬楼梯的问题,您掌握了吗?
拓展阅读:
where2go 团队
微信号:算法与编程之美
温馨提示:点击页面右下角“写留言”发表评论,期待您的参与!期待您的转发!