击败了100%的用户，还有谁！！！

大图镇楼

70. 爬楼梯 - 力扣（LeetCode）

解题思路

很明显了，用动态规划写题目。
初始状态：p[1] = 1; p[2] = 2;
递推公式：p[i] = p[i - 1] + p[i - 2]
其实动态规划就像数学归纳法一样，确定一个初始值，再确定递推关系结果就出来了。
刚开始我使用的数组存储每个状态，代码如下

第一次代码

class Solution {
   
public:
    int climbStairs(int n) {
   
        vector<int> p (n + 1 , 0);
        p[1] = 1; if(n == 1) return p[1];
        p[2] = 2; if(n == 2) return p[2];
        for(int i = 3 ; i < n + 1; i++){
   
            p[i] = p[i - 1] + p[i - 2];
        }
        return p[n];
    }
};

成功通过。但是一看才超越了16%的用户，我不服！于是仔细观察了原有的代码，进行改进。

第二次代码

改进如下：
观察代码运行，你会发现整个过程用到的变量不超过四个。
i: 迭代器
p[i]: 当前节点的值
p[i - 1]: 上一个节点的值
p[i - 2]: 上上一个节点的值
所以我把数组给去掉了，根本不需要保存那么多状态，i + xyz就够了。最终代码如下，改进后是真快啊，0毫秒。

class Solution {
   
public:
    int climbStairs(int n) {
   
        int x = 1, y = 2, z;
        if(n == 1) return x;
        if(n == 2) return y;
        for(int i = 3 ; i < n + 1; i++){
   
            z = x + y;
            x = y;
            y = z;
        }
        return z;
    }
};

本题目很简单，但是对理解动态规划很有帮助。