70.爬楼梯

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

思路

爬上n阶楼梯的方法，其实就是爬上n-1阶楼梯的方法+爬上n-2阶的方法
因为爬上n阶梯其实就是n-1阶爬1个台阶+n-2阶爬2个台阶
所以可以得到递推公式是：
2020/10/26 - 图2
注意一下边界，dp[0] =0, 因为阶梯0没有可能性

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

优化

因为其实需要保存只有上2个值，所有可以不用一个数组，只需要2个变量，这样就能优化空间

class Solution {
public:
    int climbStairs(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;

        int p = 1;
        int q = 2;
        int now;

        for(int i = 3;i <=n;i++){
            now = p + q;
            p = q;
            q = now;
        }

        return now;
    }
};

相似的题目

使用最小花费爬楼梯