题解 | #跳台阶#

#include <iostream>

using namespace std;

int climbStairs(int n) {

    static int dp[100] = {0};    // 静态数组，用于保存计算结果

    if (n == 1) {

        return 1;

    }

    if (n == 2) {

        return 2;

    }

    if (dp[n] !=

            0) {           // 如果之前已经计算过，则直接返回之前存储的结果

        return dp[n];

    }

    int result = climbStairs(n - 1) + climbStairs(n - 2); // 递推计算

    dp[n] = result;             // 保存计算结果

    return result;

}

int main() {

    int n;

    cin>>n;

    int result = climbStairs(n);

    cout << result << endl;     // 输出结果

    return 0;

}