题目

  • 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
  • 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
  • 使用C++
  • 示例 1：
    1
    2
    3
    4
    5
    输入：n = 2
    输出：2
    解释：有两种方法可以爬到楼顶。
    1. 1 阶 + 1 阶
    2. 2 阶
  • 示例 2：
    1
    2
    3
    4
    5
    6
    输入：n = 3
    输出：3
    解释：有三种方法可以爬到楼顶。
    1. 1 阶 + 1 阶 + 1 阶
    2. 1 阶 + 2 阶
    3. 2 阶 + 1 阶
  • 示例3：
    1
    2
    3
    4
    5
    6
    7
    8
    输入：n = 4
    输出：5
    解释：有五种方法可以爬到楼顶。
    1. 1 阶 + 1 阶 + 1 阶 + 1 阶
    2. 1 阶 + 2 阶 + 1 阶
    3. 2 阶 + 1 阶 + 1 阶
    4. 1 阶 + 1 阶 + 2 阶
    5. 2 阶 + 2 阶
  • 难度属于简单，题目官方的解答啰哩吧嗦的，我就按照自己的想法说说吧

动态规划

  • 每次可以选择登一阶或者两阶
  • 我们发现第n阶的登顶方法数都是在n-1阶基础上+1，以及在n-2阶的基础上+2，所以这阶的方法数就是前两阶之和
  • 用这个方法我们知道，在0阶设为1种，在1阶是1种，在2阶则是2种（因为1+1=2），以此类推第三阶则是3种（1+2=3）
  • 由此则是动态规划算法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Solution {
    public:
        int climbStairs(int n) {
            int p = 0, q = 0, r = 1;
            for(int i = 1; i <= n; i++){
                p = q;
                q = r;
                r = p + q;
            }
            return r;
        }
    };
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)