c++中如何实现动态规划爬楼梯问题_c++动态规划爬楼梯实现方法

爬楼梯问题可通过动态规划求解，状态转移方程为f(n)=f(n-1)+f(n-2)，初始条件f(0)=f(1)=1，推荐使用滚动变量法实现O(n)时间与O(1)空间复杂度。

爬楼梯问题是动态规划中的经典入门题。假设你正在爬一个有 n 阶的楼梯，每次只能走 1 阶或 2 阶，问有多少种不同的方法可以爬到楼顶？C++ 中可以通过动态规划高效解决这个问题。

问题分析与状态转移方程

设 f(n) 表示爬到第 n 阶的方法数。要到达第 n 阶，可以从第 n-1 阶走一步上来，也可以从第 n-2 阶走两步上来。因此状态转移方程为：

f(n) = f(n-1) + f(n-2)

初始条件为：
f(0) = 1（0 阶表示起点，有一种方式）
f(1) = 1（1 阶只有一种走法）

基础动态规划实现（数组存储）

使用数组保存每个阶段的结果，自底向上计算：

立即学习“C++免费学习笔记（深入）”；

#include 
using namespace std;
int climbStairs(int n) {
if (n <= 1) return 1;
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 = 5;
cout 
空间优化实现（滚动变量）
由于状态只依赖前两个值，不需要保存整个数组，可以用两个变量滚动更新：

							

								
								

									MagicArena
									
字节跳动推出的视觉大模型对战平台
								
								下载 
							
						
#include 
using namespace std;
int climbStairs(int n) {
if (n <= 1) return 1;
int prev2 = 1; // f(i-2)
int prev1 = 1; // f(i-1)
int curr;

for (int i = 2; i <= n; ++i) {
    curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
}

return prev1;
}
int main() {
int n = 6;
cout 
这种方法时间复杂度为 O(n)，空间复杂度降为 O(1)，效率更高。
递归 + 记忆化（自顶向下）
也可以用递归配合缓存避免重复计算：
#include 
#include 
using namespace std;
int dfs(int n, vector& memo) {
if (n <= 1) return 1;
if (memo[n] != -1) return memo[n];
memo[n] = dfs(n - 1, memo) + dfs(n - 2, memo);
return memo[n];
}
int climbStairs(int n) {
vector memo(n + 1, -1);
return dfs(n, memo);
}
记忆化适合理解递推关系，但性能略低于迭代法。
基本上就这些。推荐在实际编码中使用滚动变量法，简洁高效。爬楼梯问题本质是斐波那契数列的应用，关键在于识别子问题重叠和最优子结构。不复杂但容易忽略边界处理。