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

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

裘德小鎮的故事

发布： 2025-10-01 21:16:02

原创

937人浏览过

爬楼梯问题通过动态规划求解，递推关系为f(n)=f(n-1)+f(n-2)，初始条件f(0)=1、f(1)=1；2. 使用数组自底向上计算避免重复，空间优化版本用两个变量替代数组，降低空间复杂度至O(1)。

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

在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步）

实现思路

为了避免重复计算，使用数组保存已计算的结果，从下往上递推，这就是动态规划的核心思想——记忆化+自底向上。

ViiTor实时翻译

AI实时多语言翻译专家！强大的语音识别、AR翻译功能。

116

查看详情

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++++中如何实现动态规划爬楼梯_c++动态规划爬楼梯实现方法的详细内容，更多请关注php中文网其它相关文章！