题解 | #N阶楼梯上楼问题#

```#include<cstdio>
#include<iostream>
#include<vector>
using namespace std;

//简单版本
//vector<int> dp(90);
// int findStairs(int n) {    //1.dp[i]表示上到第i层有dp[i]种办法
//     dp[1] = 1;             //2.初始化从1开始，不从0开始无意义 
//     dp[2] = 2;
    
//  /*3.第i层的种数由i-1层和i-2层决定从第i-1层只需再迈一个台阶，从
//      i-2层只需再迈两个台阶，所以dp[i] = dp[i-1] + dp[i-2] 
//  */
//     for(int i = 3; i <= n; ++i) {        //4.确定遍历顺序，从前往后
//         dp[i] = dp[i - 1] + dp[i - 2];   //5.举例推导dp数组。dp[3] = 3
//     }                                    // dp[4] = 5,dp[5] = 8 
//     return dp[n];                        //时间复杂度O(n) 空间复杂度O(n)
// }  

//改进算法
int findStairs(int n) {
    int dp[3];
   dp[1] = 1;
    dp[2] = 2;
    int sum = 0;
    for (int i = 3; i <= n; ++i) {
        sum = dp[1] + dp[2];
        dp[1] = dp[2];
        dp[2] = sum;
    }
    return dp[2];
}
//时间复杂度O(n) 空间复杂度O(1)

int main() {
    int n;
    while(scanf("%d", &n) != EOF) {
        if(n <=2)
            printf("%d\n", n);
        else {
            int m = findStairs(n);
            printf("%d\n", m);
        }
    }
}
``` js