leetcode：70. 爬楼梯

题目

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

示例：

  1. 输入：n = 2
  2. 输出：2
  3. 解释：有两种方法可以爬到楼顶。
  4. 1. 1 阶 + 1 阶
  5. 2. 2 阶
  1. 输入：n = 3
  2. 输出：3
  3. 解释：有三种方法可以爬到楼顶。
  4. 1. 1 阶 + 1 阶 + 1 阶
  5. 2. 1 阶 + 2 阶
  6. 3. 2 阶 + 1 阶

解答 & 代码

动态规划：

  • 动态规划数组 dp：dp[i] 代表爬到 i 阶楼梯的方法数
  • 状态转移方程：dp[i] = dp[i - 2] + dp[i - 1]
    • 最后一步可以走 2 阶 or 1 阶。如果最后一步走 2 阶，则方法数 = dp[i - 2]；如果最后一步走 1 阶，则方法数 = dp[i - 1]
  • 初始化：dp[1] = 1, dp[2] = 2

由于每个状态之和前两个状态有关，所以不需要用 dp 数组，只用两个变量记录之前的两个状态即可

  1. class Solution {
  2. public:
  3.     int climbStairs(int n) {
  4.         if(n <= 2)
  5.             return n;
  7.         int dp1 = 1;
  8.         int dp2 = 2;
  9.         for(int i = 3; i <= n; ++i)
  10.         {
  11.             int dp = dp1 + dp2;        // dp[i] = dp[i - 2] + dp[i - 1]
  12.             dp1 = dp2;
  13.             dp2 = dp;
  14.         }
  15.         return dp2;
  16.     }
  17. };

复杂度分析：设楼梯阶梯数为 n

  • 时间复杂度 O(n)：一次遍历
  • 空间复杂度 O(1)：

执行结果：

  1. 执行结果：通过
  3. 执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
  4. 内存消耗：5.8 MB, 在所有 C++ 提交中击败了 70.49% 的用户