当前位置：首页 > news >正文

动态规划算法详解（C++）

news 2025/4/26 12:01:46

动态规划（Dynamic Programming，DP）是一种通过将复杂问题分解为重叠子问题并存储中间结果来优化计算的算法设计方法。其核心思想是避免重复计算，通过空间换时间提高效率。

动态规划核心要素

重叠子问题
问题可以被分解为多个重复出现的子问题（如斐波那契数列）。
最优子结构
问题的最优解包含其子问题的最优解（如最短路径问题）。
状态转移方程
定义子问题之间的关系式，描述如何从已知状态推导新状态。

动态规划实现步骤

定义状态
明确问题状态（如 dp[i] 或 dp[i][j] 的含义）。
状态转移方程
建立状态间的递推关系。
初始化边界条件
设置初始值（如 dp[0] = 0）。
计算顺序
确定填充状态表的顺序（自底向上或记忆化搜索）。

经典动态规划问题及C++实现

1.斐波那契数列（重叠子问题）

问题：计算第n个斐波那契数列（F(n) = F(n - 1) + F(n -2)）。

解决方法：递归法和动态规划法

递归法缺陷：存在大量重复计算（指数复杂度）。
动态规划优化：存储中间结果（线性复杂度）。

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int fibonacci(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];
}int main(){cout << fibonacci(10); // 输出55return 0;}

2.最长公共子序列（LCS）

问题：给定两个字符串text1 和 text2,返回它们的最长公共子序列长度。

示例：

输入：text1 = "abcde", text2 = "ace"

输出：3

解释：最长公共子序列是"ace",它的长度为3。

状态定义：dp[i][j] 表示 text[0...i-1] 和 text[0...j-1]的最长公共子序列长度。

状态转移：

若 text1[i-1] == text2[j-1],则dp[i][j] = dp[i-1][j-1]+1

否则，dp[i][j] = max(dp[i-1][j],dp[i][j- 1])

#include <iostream>
#include <vector>
using namespace std;int longestCommonSubsequence(string text1, string text2){int m = text1.size(), n = text2.size();vector<vector<int>> dp(m + 1, vector<int>(n+1,0));for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){if(text1[i - 1] == text2[j - 1]){dp[i][j] = dp[i - 1][j - 1] + 1;}else{dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);    }}}return dp[m][n];
}int main(){cout << longestCommonSubsequence("abcde", "ace"); // 输出3cin.get();return 0;}

3.0-1背包问题（最优子结构）

问题：给定物品重量 weight[] 和价值 value[] , 容量为 W 的背包，求价值总和最大值。即假设你有一个背包，背包能承受最大重量 W，你有 n 个物品。每个物品有一个重量和一个价值，你的目标是选择一些物品放入背包，使得总重量不超过背包容量 W，同时总价值最大。每个物品只能选择一次。

示例：背包容量17kg的经典案例

在总重量时17kg的限制下，选出价值相加最高的一些物品。

物品序号	重量(kg)	价值(元)
1	2	6
2	2	3
3	6	5
4	5	4
5	4	6

答案：21

解释：在总重量是17kg的限制下价值相加最高的选择是1、3、4、5，总价值是21元。

状态定义： dp[i][w] 表示前 i 个物品在容量 w 下的最大价值。

状态转移：

若 weight[i - 1] > w, 不选： dp[i][w] = dp[i - 1][w]

否则，选或不选的最大值：dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i-1]] + value[i-1])

代码示例：

#include <iostream>
#include <vector>
using namespace std;int knapsack(int W, vector<int>& weight, vector<int>& value) {int n = weight.size();vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));for (int i = 1; i <= n; i++) {for (int w = 1; w <= W; w++) {if (weight[i - 1] > w) {dp[i][w] = dp[i - 1][w];}else {dp[i][w] = max(dp[i - 1][w],dp[i - 1][w - weight[i - 1]] + value[i - 1]);}}}return dp[n][W];
}int main() {vector<int> weight = { 2, 2, 6, 5, 4 };vector<int> value = { 6, 3, 5, 4, 6 };cout << knapsack(17, weight, value);  // 输出21cin.get();return 0;
}

代码解析：

函数定义和初始化：

int knapsack(int W, vector<int>& weight, vector<int>& value){int n = weight.size(); // 获取物品的数量vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0))// 创建动态规划表格

W 是背包的最大容量。
weight 是一个数组，表示每个物品的重量。
value 是一个数组，表示每个物品的价值。
dp[i][w] 表示考虑前 i 个物品，且背包容量为 w 时的最大价值。

动态规划表 dp 的大小是 (n+1) * (W+1)，其中 n 是物品数，W 是背包容量。初始时，所有值都设为 0，意味着如果没有选择任何物品，价值为 0。

2.填充动态规划表格：

    for (int i = 1; i <= n; i++) {for (int w = 1; w <= W; w++) {if (weight[i - 1] > w) {dp[i][w] = dp[i - 1][w];  // 当前物品不能放入背包}else {dp[i][w] = max(dp[i - 1][w],dp[i - 1][w - weight[i - 1]] + value[i - 1]);  // 选择放入或不放入当前物品}}}

这个部分是动态规划的核心。我们通过两层循环来填充 dp 数组。

外层循环 i 遍历所有物品，从第 1 个物品到第 n 个物品。
内层循环 w 遍历所有可能的背包容量，从 1 到 W。

其中，

if (weight[i - 1] > w) {dp[i][w] = dp[i - 1][w];
}

这行代码的作用是 处理当前物品的重量超过背包容量的情况。dp[i][w] 表示考虑前 i 个物品，在背包容量为 w 时能获得的最大价值。如果当前物品的重量大于当前背包容量（即 weight[i - 1] > w），这意味着我们不能将这个物品放入背包中，因为它的重量超过了背包剩余的容量。在这种情况下，我们只能选择不放入这个物品。因此，dp[i][w] 就应该等于 不放入当前物品时的最大价值，即 dp[i - 1][w]。这意味着我们还是只考虑前 i-1 个物品，背包容量保持为 w，不增加当前物品。

例如，第一轮循环中，即i=1,w=1,i=1表示第一个物品，根据weight = { 2, 2, 6, 5, 4 }，其重量为2，背包当前容量 w = 1。显然，当前物品的重量 2 大于背包容量 1，所以我们无法选择该物品。

在这种情况下：

if (weight[i - 1] > w) {dp[i][w] = dp[i - 1][w];
}

就会执行：

dp[1][1] = dp[0][1]; // dp[0][1]在dp创建时被初始化为0，即dp[0][1] = 0

这意味着 第 1 个物品不能放入背包，所以我们选择没有物品放入时的最大价值，即0。

再假设我们有以下情况：

当前物品 i = 3，其重量为 6，价值为 5。
背包当前容量 w = 4。

显然，当前物品的重量 6 大于背包容量 4，所以我们无法选择该物品。

就会执行：

dp[3][4] = dp[2][4];

这意味着 第 3 个物品不能放入背包，所以我们选择前 2 个物品在容量为 4 时的最大价值（即不放入第 3 个物品）。

if (weight[i - 1] > w) {dp[i][w] = dp[i - 1][w];
}

总之，这段代码的作用就是保证如果当前物品的重量超过了背包的容量，那么我们就不能把它放入背包，dp[i][w] 直接继承自 dp[i - 1][w]，即保持背包容量为 w 时的最优解，不受当前物品影响。

else {dp[i][w] = max(dp[i - 1][w],dp[i - 1][w - weight[i - 1]] + value[i - 1]);
}

这段代码的作用是处理 可以选择放入当前物品 的情况。它是 0/1 背包问题 动态规划算法中的核心部分。具体来说，假设我们正在考虑第 i 个物品，并且当前背包的容量为 w，我们有两种选择：

不放入当前物品：我们不考虑当前物品，那么背包的最大价值就等于不考虑当前物品的情况下的最大价值，即 dp[i-1][w]。

放入当前物品：我们选择将当前物品放入背包，那么背包的容量减少，新的容量是 w - weight[i-1]，同时，我们的总价值增加了当前物品的价值 value[i-1]，此时的最大价值是 dp[i-1][w - weight[i-1]] + value[i-1]。

动态规划算法和贪心算法的区别

动态规划算法（Dynamic Programming, DP）和贪心算法（Greedy Algorithm）都是常用的算法设计策略，用于求解优化问题。但它们的思路和应用场景有很大的不同。下面是这两种算法的主要区别：

1. 问题类型

动态规划：适用于 具有重叠子问题 和 最优子结构 的问题。重叠子问题指的是在递归求解过程中，某些子问题会多次出现，而最优子结构表示一个问题的最优解可以通过其子问题的最优解来构建。

例子：背包问题、最长公共子序列、最短路径问题等。
贪心算法：适用于贪心选择性质的优化问题，贪心选择性质表示在求解问题的过程中，可以通过选择当前最优的局部解来构造全局最优解。这意味着每一步的选择都是局部最优的，并不考虑后续的影响。

例子：活动选择问题、最小生成树问题（Kruskal 和 Prim 算法）、霍夫曼编码等。

2. 算法策略

动态规划：
- 全局优化：动态规划通过分解问题并利用子问题的解来构造全局解。它通常通过 自底向上 或 自顶向下 的方式来求解，使用一个表格或数组来保存已经计算过的子问题的解，以避免重复计算。
- 需要考虑所有的可能解，并通过计算每个子问题的最优解来逐步构建全局最优解。
贪心算法：
- 局部优化：贪心算法从问题的当前状态出发，做出局部最优的选择，而不考虑整体后果。它通过逐步选择当前最佳选项来求解问题。
- 贪心算法并不回溯或考虑后续步骤，因此它通常不适用于那些 不满足贪心选择性质 的问题。

3. 解的质量

动态规划：能保证求得全局最优解，因为它会考虑到所有的子问题，并综合考虑每一步的决策。
贪心算法：贪心算法并不一定能得到全局最优解，它只保证在每个局部选择上是最优的。在某些问题中，贪心算法能够给出全局最优解，但在其他问题中，它可能只给出次优解。

4. 时间和空间复杂度

动态规划：由于动态规划需要存储子问题的解（通常是二维或多维数组），因此它的空间复杂度较高。而且动态规划的时间复杂度通常是多项式级别，因为它需要遍历所有可能的子问题并求解。
- 时间复杂度：通常是 O(n^2)、O(n^3) 等。
- 空间复杂度：通常是 O(n) 或 O(n^2)。
贪心算法：通常只需要局部信息，空间复杂度较低。时间复杂度一般较低，通常是 O(n log n)（如排序操作），甚至是 O(n)（如某些选择问题）。
- 时间复杂度：通常是 O(n log n) 或 O(n)。
- 空间复杂度：通常是 O(1)（只需要常量空间，除非有额外的数据结构）。

5. 算法实现

动态规划：
- 通常需要记忆化（memoization）或者填充一个表格（tabulation）来存储子问题的解。
- 过程较复杂，通常需要设计状态转移方程，并且需要处理子问题的依赖关系。
贪心算法：
- 实现起来通常比较简单。需要定义一个贪心策略，并在每一步选择当前最优的选项。
- 过程相对直观，但需要注意选择的贪心策略是否适用于问题的全局最优解。

6. 适用场景

动态规划：
- 适合 重叠子问题 的情况，通常在问题中存在某种形式的递归结构（子问题可以重复求解），且子问题的解可以合并成原问题的解。
例子：
- 背包问题、最长公共子序列问题、编辑距离、最短路径问题等。
贪心算法：
- 适合 贪心选择性质 存在的场景，即每一步做出局部最优选择最终能得到全局最优解。
例子：
- 活动选择问题、最小生成树问题、霍夫曼编码等。

总结表格

特性	动态规划（DP）	贪心算法（Greedy）
问题类型	重叠子问题，最优子结构	贪心选择性质
算法策略	全局优化（考虑所有子问题的解）	局部优化（只关注当前最优选择）
解的质量	保证全局最优解	不一定是全局最优解
时间复杂度	一般较高，通常是多项式 `O(n^2)` 或更高	通常较低，`O(n log n)` 或 `O(n)`
空间复杂度	较高，通常需要存储子问题的解	较低，通常只需要常数空间
适用场景	背包问题、最长公共子序列、最短路径等	活动选择问题、最小生成树、霍夫曼编码等