算法简单题，吾辈重拳出击 - 动态规划之爬楼梯
携手创作，共同成长！这是我参与「掘金日新计划 · 8 月更文挑战」的第2天，点击查看活动详情
DP 动态规划接着冲！经典之爬楼梯题目~
image.png
题：
假设你正在爬楼梯。需要
n阶你才能到达楼顶。 每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶1 <= n <= 45
解：
看完题目，但又一点思路没有，可以尝试枚举。很多算法题都是这样，没有思路，就枚举几个，思路就会来了。
在示例的基础上，再加几个示例，加到有思路为止🐶：
n = 1
1. 1n = 2
1. 1+1
2. 2n = 3
1. 1+1+1
2. 1+2
3. 2+1n = 4
1. 1+1+1+1
2. 1+1+2
3. 1+2+1
4. 2+1+1
5. 2+2n = 5
1. 1+1+1+1+1
2. 1+1+1+2
3. 1+1+2+1
4. 1+2+1+1
5. 2+1+1+1
6. 2+1+2
7. 1+2+2
8. 2+2+1n = 6
1. 1+1+1+1+1+1
2. 1+1+1+1+2
3. 1+1+1+2+1
4. 1+1+2+1+1
5. 1+2+1+1+1
6. 2+1+1+1+1
7. 1+1+2+2
8. 1+2+1+2
9. 1+2+2+1
10. 2+1+2+1
11. 2+1+1+2
12. 2+2+1+1
13. 2+2+2......
方法数依次为：1、2、3、5、8、13......
就纯数学角度来看，观察这个数列，找规律，这不就是斐波那契数列吗？
每一项等于前两项的和：
f(x)=f(x-1)+f(x-2)
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
let a = 1
if(n===1) return 1
let b = 2
if(n===2) return 2
let res = 0
for(let i=0;i<n-2;i++){
res = a+b
a = b
b = res
}
return res
} 
image.png
用 动态规划 的思维来解释上述斐波那契数列，就不用枚举找规律了：
将本题问题分成多个子问题：
爬第n阶楼梯的方法数量 = （爬上 n−1 阶楼梯的方法数量）+（爬上 n−2 阶楼梯的方法数量）
用表达式表达即：dp[n]=dp[n−1]+dp[n−2]
var climbStairs = function(n) {
const dp = [];
dp[0] = 1;
dp[1] = 1;
for(let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
};小结：
动态规划的很多题，思维都是考虑最后一项和前面一项或多项的关系，将一个大问题抽象为一个小的具体的表达式。
OK，以上便是本篇分享。点赞关注评论，为好文助力👍 我是掘金安东尼 🤠 100 万人气前端技术博主 💥 INFP 写作人格坚持 1000 日更文 ✍ 关注我，安东尼陪你一起度过漫长编程岁月 🌏
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-08-02，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
