C++怎么实现动态规划算法_C++算法设计与动态规划实现-C++-PHP中文网

C++怎么实现动态规划算法_C++算法设计与动态规划实现

穿越時空

发布： 2025-11-18 16:35:02

原创

152人浏览过

动态规划通过分解问题为子问题求解复杂问题，C++因高效与灵活适合实现。核心思想是最优子结构和重叠子问题，常用自顶向下（记忆化搜索）和自底向上（递推）两种方法。以斐波那契数列为入门案例，展示从暴力递归到记忆化再到递推及空间优化的演进过程。背包问题体现状态定义与转移方程设计，0-1背包使用二维DP数组或滚动数组进行空间优化。关键技巧包括明确状态含义、写出转移方程、初始化边界、控制遍历顺序及压缩空间。掌握经典模型如斐波那契、背包、LCS、LIS等可举一反三，结合C++ vector 等容器提升实现效率。

c++怎么实现动态规划算法_c++算法设计与动态规划实现

动态规划（Dynamic Programming，简称DP）是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。C++ 由于其高效的执行速度和灵活的语法特性，非常适合实现动态规划算法。下面介绍动态规划的基本思想以及在 C++ 中的常见实现方式。

动态规划的核心思想

动态规划适用于具有重叠子问题和最优子结构的问题：

最优子结构：问题的最优解包含其子问题的最优解。
重叠子问题：递归过程中重复计算相同的子问题，使用记忆化避免重复计算。

常见的解决方式有两种：

自顶向下（记忆化搜索）：用递归+缓存已计算结果。
自底向上（递推 + 数组）：从小规模问题开始逐步构建大问题的解。

经典案例：斐波那契数列

斐波那契数列是理解动态规划最基础的例子：
F(0)=0, F(1)=1, F(n)=F(n−1)+F(n−2)

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

暴力递归（效率低）：

#include <iostream>
using namespace std;
<p>int fib(int n) {
if (n <= 1) return n;
return fib(n-1) + fib(n-2);
}</p>

登录后复制

记忆化搜索（自顶向下）：

#include <iostream>
#include <vector>
using namespace std;
<p>int dfs(int n, vector<int>& memo) {
if (n <= 1) return n;
if (memo[n] != -1) return memo[n];
memo[n] = dfs(n-1, memo) + dfs(n-2, memo);
return memo[n];
}</p><p>int fib(int n) {
vector<int> memo(n+1, -1);
return dfs(n, memo);
}</p>

登录后复制

递推法（自底向上，推荐）：

int fib(int n) {
    if (n <= 1) return n;
    vector<int> dp(n+1);
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

登录后复制

空间优化版本（只保留前两个状态）：

小绿鲸英文文献阅读器

英文文献阅读器，专注提高SCI阅读效率

352

查看详情

int fib(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; ++i) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

登录后复制

背包问题示例：0-1 背包

给定 N 个物品，每个物品有重量 w[i] 和价值 v[i]，一个容量为 W 的背包，求能装下的最大总价值（每件物品只能选或不选）。

状态定义：

dp[i][w] 表示前 i 个物品在总重量不超过 w 时的最大价值。

状态转移方程：

不选第 i 个物品：dp[i][w] = dp[i-1][w]
选第 i 个物品（前提 w ≥ w[i]）：dp[i][w] = dp[i-1][w-w[i]] + v[i]
取两者最大值。

C++ 实现：

#include <iostream>
#include <vector>
using namespace std;
<p>int knapsack(int N, int W, vector<int>& weights, vector<int>& values) {
vector<vector<int>> dp(N+1, vector<int>(W+1, 0));</p><pre class='brush:php;toolbar:false;'>for (int i = 1; i <= N; ++i) {
    for (int w = 0; w <= W; ++w) {
        dp[i][w] = dp[i-1][w]; // 不选
        if (weights[i-1] <= w) {
            dp[i][w] = max(dp[i][w], dp[i-1][w - weights[i-1]] + values[i-1]);
        }
    }
}
return dp[N][W];

登录后复制

}

空间优化（滚动数组）：

int knapsack_optimized(int N, int W, vector<int>& weights, vector<int>& values) {
    vector<int> dp(W+1, 0);
    for (int i = 0; i < N; ++i) {
        for (int w = W; w >= weights[i]; --w) { // 倒序更新
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

登录后复制