题目
假设你正在爬楼梯。需要 n
阶你才能到达楼顶。
每次你可以爬 1
或 2
个台阶。你有多少种不同的方法可以爬到楼顶呢?
示例 1:
输入:n = 2
输出:2
解释:有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2:
输入:n = 3
输出:3
解释:有三种方法可以爬到楼顶。
- 1.阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
提示:
1 <= n <= 45
思路
第1阶 1步
第2阶 2步
第3阶 3步
第4阶 5步
第5阶 8步
第6阶 13步
根据每一阶得到的规律可以推导公式为dp[n] = dp[n-1] + dp[n-2]
,所以根据此公式进行动态规划。
- 确定
dp[n]
的含义:第n
级台阶需要dp[n]
种不同的方法达到 - 确定递推公式:
dp[n] = dp[n-1] + dp[n-2]
- dp数组如何初始化:因为题目中说明第0阶是没有意义的,所以dp[0]等于1或者0都可以,但是对于题目的规律来说dp[0]=1更便于后面的计算。
- 确定遍历顺序:因为要计算当前元素值就需要确定前两个元素的值,所以应当是从前往后进行遍历。
- 举例推导dp数组:和斐波那契数列一样
代码
class Solution {
public:
int climbStairs(int n) {
if(n<=1) return 1;//设定dp[0]=1;dp[1]=1;因为题目中说明第0阶是没有意义的,所以dp[0]等于1或者0都可以,但是对于题目的规律来说dp[0]=1更便于后面的计算。
vector<int> dp(n+1); //创建一个长度为n+1的数组
dp[1]=1;//赋初值
dp[2]=2;//赋初值
for(int i=3;i<=n;i++)//从第三个元素开始遍历,因为第三个元素的值是前两个元素值相加的结果
{
dp[i]=dp[i-2]+dp[i-1];
}
return dp[n];//最后返回dp[n]的值
}
};
1 条评论
您好,看你的站做的挺不错的,有没有出手的打算,想出手的话,联系QQ1587894193。