题目

点击查看原题

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 12个台阶。你有多少种不同的方法可以爬到楼顶呢?

示例 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

思路

第1阶 1步
第2阶 2步
第3阶 3步
第4阶 5步
第5阶 8步
第6阶 13步

根据每一阶得到的规律可以推导公式为dp[n] = dp[n-1] + dp[n-2] ,所以根据此公式进行动态规划。

  1. 确定dp[n]的含义:第n级台阶需要dp[n]种不同的方法达到
  2. 确定递推公式:dp[n] = dp[n-1] + dp[n-2]
  3. dp数组如何初始化:因为题目中说明第0阶是没有意义的,所以dp[0]等于1或者0都可以,但是对于题目的规律来说dp[0]=1更便于后面的计算。
  4. 确定遍历顺序:因为要计算当前元素值就需要确定前两个元素的值,所以应当是从前往后进行遍历。
  5. 举例推导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]的值
    }
};
End

本文标题:LeetCode 第70题 爬楼梯

本文链接:http://chisato.cn/index.php/archives/196/

除非另有说明,本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

声明:转载请注明文章来源。

最后修改:2022 年 07 月 25 日 11 : 02 PM
如果觉得我的文章对你有用,请随意赞赏