台阶问题：小瓜的爬楼梯方案

小瓜想通过台阶走上平台，最底层（小瓜所在的层）编号为 '1'，最顶层编号为 'n'。由于小瓜的腿比较短，他一次只能向上走 '1' 级或者 '2' 级台阶。小瓜想知道他有多少种方法走上平台，你能帮帮他吗？

输入

一个整数 'n'，其中 '1 <= n <= 100'。

输出

一行一个整数，表示小瓜上台阶的方案数

C++ 代码

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> dp(n+1, 0);
    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }

    cout << dp[n] << endl;

    return 0;
}

算法解析:

这道题可以使用动态规划来解决。我们用 dp[i] 表示到达第 'i' 层的方案数。

显然，到达第 '0' 层和第 '1' 层都只有一种方案，即 dp[0] = 1 和 dp[1] = 1。
对于 'i > 1' 的情况，到达第 'i' 层的方案数可以分为两种情况：
- 从第 'i-1' 层爬1级到达第 'i' 层，方案数为 dp[i-1]。
- 从第 'i-2' 层爬2级到达第 'i' 层，方案数为 dp[i-2]。
因此，到达第 'i' 层的方案数 dp[i] 等于 dp[i-1] 和 dp[i-2] 的和，即 dp[i] = dp[i-1] + dp[i-2]。

代码解析:

使用 vector<int> dp(n+1, 0) 创建一个大小为 'n+1' 的数组 dp，用于存储到达每个台阶的方案数。
初始化 dp[0] = 1 和 dp[1] = 1，表示到达第 '0' 层和第 '1' 层的方案数。
使用循环遍历 'i' 从 '2' 到 'n'，根据动态规划公式 dp[i] = dp[i-1] + dp[i-2] 计算每个 dp[i]。
最后输出 dp[n]，即到达第 'n' 层的方案数。