参考：点击查看

算法实现步骤：

  • 确定dp数组以及下标的含义
    定义 dp[i] 为爬上第 i 级台阶有多少种方案；
  • 确定状态转移方程
    因为每次只可以爬 1 或者 2 个台阶所以，爬上当前台阶的方案应该是前面两个状态的方案的和，即dp[i]=dp[i−1]+dp[i−2]
  • 初始化状态
    i=0级开始爬的，所以从第 0 级爬到第0级我们可以看作只有一种方案，即 dp(0)=1；
    i=1代表从第 0级到第 1级也只有1种方案，爬一级，即dp(1)=1。
  • 遍历顺序
    由状态转移方程知道 dp[i] 是从 dp[i−1] 和 dp[i−2] 转移过来所以从前往后遍历。
  • 返回值
    因为一共计算 n 阶楼梯有多少方案，所以返回 dp[n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/* 动态规划五部曲：
     * 1.确定dp[i]的下标以及dp值的含义： 爬到第i层楼梯，有dp[i]种方法；
     * 2.确定动态规划的递推公式：dp[i] = dp[i-1] + dp[i-2];
     * 3.dp数组的初始化：因为提示中，1<=n<=45 所以初始化值，dp[1] = 1, dp[2] = 2;
     * 4.确定遍历顺序：分析递推公式可知当前值依赖前两个值来确定，所以递推顺序应该是从前往后；
     * 5.打印dp数组看自己写的对不对；
*/
#include<iostream>
#include <vector>
using namespace std;
class Solution_origin {
public:
    int climbStairs(int n) {
        if (n <= 1) return n;
        /* 定义dp数组 */
        vector<int> dp(n+1);
        /* 初始化dp数组 */
        dp[1] = 1;
        dp[2] = 2;
        /* 从前往后遍历 */
        for(int i = 3; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};

利用滚动数组思想将空间复杂度限制在O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/* 动态规划五部曲：
     * 1.确定dp[i]的下标以及dp值的含义： 爬到第i层楼梯，有dp[i]种方法；
     * 2.确定动态规划的递推公式：dp[i] = dp[i-1] + dp[i-2];
     * 3.dp数组的初始化：因为提示中，1<=n<=45 所以初始化值，dp[1] = 1, dp[2] = 2;
     * 4.确定遍历顺序：分析递推公式可知当前值依赖前两个值来确定，所以递推顺序应该是从前往后；
     * 5.打印dp数组看自己写的对不对；
*/
#include<iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int climbStairs(int n) {
        /* 定义dp数组 */
        vector<int> dp(3);
        /* 初始化dp数组 */
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        /* 从前往后遍历 */
        for(int i = 3; i <= n; i++) {
            dp[i%3] = dp[(i-1)%3] + dp[(i-2)%3];
        }
        return dp[n%3];
    }
};
int main(){
    int a;
    Solution sample;
    a=sample.climbStairs(5);    cout<<a;
}