c++DP代码春天到了，程小盟和同学们一起去春游。他们来到了华山脚下看着笔直石头台阶都非常感叹。这时同学们中间有几个同学提出了一个问题发生争执，华山总共有 M 台阶，如果同学们刚开始都站在第 1 个台阶级，每次只能跨上 1 级或 2 级，要走上山顶，会有多少多少种走法呢？

这个问题是一个典型的动态规划（Dynamic Programming, DP）问题，通常被称为“爬楼梯”或“台阶问题”。在 C++ 中，我们可以使用二维数组来解决。假设 `dp[i]` 表示到达第 i 个台阶的不同走法数。

首先，初始化两个变量：`dp[0] = 1`（走到第 0 阶就是直接上去），`dp[1] = 1`（走到第 1 阶只有一步可以走）。然后从第二阶开始遍历到 M 阶：

对于每个台阶 `i`（从 2 到 M），有两种情况：
1. 如果上一步走了 1 级，那么到达第 i 级的方法是从第 i-1 阶走过来的，所以 dp[i] = dp[i-1]。
2. 如果上一步走了 2 级，那么到达第 i 级的方法是从第 i-2 阶走过来的，所以 dp[i] += dp[i-2]。

最后的结果 `dp[M]` 就是到达山顶的所有可能走法。

C++ 代码示例：

#include <iostream>
using namespace std;

int climbStairs(int n) {
    int dp[n + 1];
    dp[0] = 1;
    dp[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]; // 动态转移方程
    }
    
    return dp[n];
}

int main() {
    int M;
    cout << "请输入台阶总数：";
    cin >> M;
    cout << "有 " << climbStairs(M) << " 种走法。\n";
    return 0;
}