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

N阶楼梯上楼问题

本题为经典的动态规划问题

动态规划相比于暴力的递归解法的区别在于动态规划法合理利用已经求解过的子问题用来求解最终的问题

动态规划的关键点在：

1. 记忆数组：dp用来记忆每次求解的子问题
2. 递推公式：dp[n] = dp[n-1] + dp[n-2];
3. 初始条件：dp[1]第一阶台阶的登上方法只有一种，dp[2]第二阶台阶的登上方法有两种，以此初始条件进行递推即可

#include <vector>
using namespace std;

int main()
{
    vector<int> dp(90);
    int n;

    while (cin >> n) {
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        cout << dp[n] << endl;
    }
    
    return 0;
}