爬楼梯问题通过动态规划求解，递推关系为f(n)=f(n-1)+f(n-2)，初始条件f(0)=1、f(1)=1；2. 使用数组自底向上计算避免重复，空间优化版本用两个变量替代数组，降低空间复杂度至O(1)。
在C++中，动态规划（Dynamic Programming, DP）是解决“爬楼梯”问题的经典方法。这个问题的描述通常是：每次可以爬1阶或2阶台阶，问爬到第n阶有多少种不同的走法。
问题分析
假设要到达第n阶，最后一步可能是从第n-1阶跨1步上来，也可能是从第n-2阶跨2步上来。因此，到达第n阶的方法数等于到达第n-1阶和第n-2阶的方法数之和。
这形成了一个递推关系：
f(n) = f(n-1) + f(n-2)
立即学习“C++免费学习笔记（深入）”；
初始条件为：
f(0) = 1（表示站在地面不动也算一种方式）
f(1) = 1（只能跨1步）
实现思路
为了避免重复计算，使用数组保存已计算的结果，从下往上递推，这就是动态规划的核心思想——记忆化+自底向上。
千面视频动捕
27
千面视频动捕是一个AI视频动捕解决方案，专注于将视频中的人体关节二维信息转化为三维模型动作。
27
查看详情
C++代码实现
#include <iostream>
#include <vector>
using namespace std;
<p>int climbStairs(int n) {
if (n <= 1) return 1;</p><pre class='brush:php;toolbar:false;'>vector<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 n;
cout << “请输入楼梯阶数: “;
cin >> n;
cout << "爬到第 " << n << " 阶共有 " << climbStairs(n) << " 种方法。\n"; return 0;
}
空间优化版本
由于状态转移只依赖前两个值，不需要保存整个dp数组，可以用两个变量代替，降低空间复杂度至O(1)。
int climbStairs(int n) {
if (n <= 1) return 1;
<pre class='brush:php;toolbar:false;'>int prev2 = 1; // f(0)
int prev1 = 1; // f(1)
int curr;
for (int i = 2; i <= n; ++i) {
curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return curr;
}
这个优化版本在逻辑上与原DP一致，但更节省内存，适合处理大数值（注意int溢出问题，可改用long long）。
基本上就这些，理解状态转移方程是关键。
相关标签：
c++ ai ios stream int cin
本站资料仅供学习交流使用请勿商业运营，严禁从事违法，侵权等任何非法活动，否则后果自负！
THE END
暂无评论内容