题目描述

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

题解

这道题是一个非常典型而且很简单的动态规划题目。我们可以根据动态规划题目解题的一般思路来分析：

  1. 定义状态：

$dp[i]$表示爬到第$i$级楼梯的不同方法数。由于每次可以选择爬 $1$ 级或者 $2$ 级楼梯， 所以爬到第 $i$ 级楼梯的方法数等于爬到第 $i-1$ 级楼梯和第 $i-2$ 级楼梯的方法数之和。 根据这个关系，我们可以使用动态规划的方式从 $1$ 级楼梯开始逐步计算到第 $n$ 级楼梯的方法数，最终返回 $dp[n]$即为结果。

  1. 设计状态转移方程：

$$dp[i] = dp[i - 1] + dp[i - 2]$$

  1. 初始化：

由题目可知，$dp[0] = 0$; $dp[1] = 1$，这里需要特别注意的是，$dp[2] \ne dp[0] + dp[1]$，而是$dp[2] = 2$，所以$dp[2]$也应该作为初始值

  1. 递推求解：
#include <vector>

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        std::vector<int> dp(n + 1);
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};
  1. 记忆优化：

从上面代码可以很容易发现，我们得出$dp[i]$只需要用到$dp[i - 1]$和$dp[i -2]$，其他的元素其实都用不到，所以上面的代码可以优化为：

#include <vector>

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        int pp = 1;
        int p = 2;
        int c = 0;
        for (int i = 3; i <= n; ++i) {
            c = pp + p;
            pp = p;
            p = c;
        }
        return c;
    }
};