c++中如何实现动态规划爬楼梯问题_c++动态规划爬楼梯实现方法-C++-PHP中文网

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

穿越時空

发布： 2025-10-03 08:35:02

原创

673人浏览过

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

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

爬楼梯问题是动态规划中的经典入门题。假设你正在爬一个有 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 <iostream>
using namespace std;
<p>int climbStairs(int n) {
if (n <= 1) return 1;</p><pre class='brush:php;toolbar:false;'>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 << "爬到第 " << n << " 阶的方法数: " << climbStairs(n) << endl; return 0; }

空间优化实现（滚动变量）

由于状态只依赖前两个值，不需要保存整个数组，可以用两个变量滚动更新：

Tanka

具备AI长期记忆的下一代团队协作沟通工具

110

查看详情

#include <iostream>
using namespace std;
<p>int climbStairs(int n) {
if (n <= 1) return 1;</p><pre class='brush:php;toolbar:false;'>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 << "爬到第 " << n << " 阶的方法数: " << climbStairs(n) << endl; return 0; }

这种方法时间复杂度为 O(n)，空间复杂度降为 O(1)，效率更高。

递归 + 记忆化（自顶向下）

也可以用递归配合缓存避免重复计算：

#include <iostream>
#include <vector>
using namespace std;
<p>int dfs(int n, vector<int>& memo) {
if (n <= 1) return 1;
if (memo[n] != -1) return memo[n];</p><pre class='brush:php;toolbar:false;'>memo[n] = dfs(n - 1, memo) + dfs(n - 2, memo);
return memo[n];

登录后复制

}

int climbStairs(int n) { vector<int> memo(n + 1, -1); return dfs(n, memo); }

记忆化适合理解递推关系，但性能略低于迭代法。

基本上就这些。推荐在实际编码中使用滚动变量法，简洁高效。爬楼梯问题本质是斐波那契数列的应用，关键在于识别子问题重叠和最优子结构。不复杂但容易忽略边界处理。

以上就是c++++中如何实现动态规划爬楼梯问题_c++动态规划爬楼梯实现方法的详细内容，更多请关注php中文网其它相关文章！