深入理解动态规划算法 - 爬楼梯
欢迎点击「算法与编程之美」↑关注我们！
本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。
问题描述
一个楼梯有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 团队
微信号：算法与编程之美
温馨提示：点击页面右下角“写留言”发表评论，期待您的参与！期待您的转发！