动态规划（Dynamic Programming, DP）是一种解决复杂问题的算法计划技术，它通过将大问题分解为小问题，并利用小问题的解决方案来构造大问题的解决方案，从而制止了重复盘算。动态规划通常用于具有“最优子结构”和“重叠子问题”特性的问题。
动态规划的根本步骤
- 界说状态：明确问题的状态表现。即怎样用状态表现当前的子问题。
- 状态转移方程：根据问题的结构，找到从一个状态转移到另一个状态的方式。
- 初始化：为根本情况设置初始值。
- 盘算顺序：确定盘算的顺序，从最小的子问题开始渐渐盘算到原问题。
- 答案提取：从动态规划表中提取最终答案。
动态规划的典型应用场景
- 最短路径问题（如 Dijkstra、Floyd 算法）。
- 背包问题（如 0/1 背包、完全背包）。
- 字符串匹配问题（如最长公共子序列、编辑间隔）。
- 最优子结构问题（如矩阵链乘法问题、切割钢条问题）。
动态规划的分类
动态规划的算法通常可以分为以下两种类型：
- 自顶向下的递归式动态规划（Top-Down with Memoization）：
利用递归进行问题的求解，并通过记忆化（Memoization）保存已盘算的结果，制止重复盘算。
- 自底向上的迭代式动态规划（Bottom-Up with Tabulation）：
通过迭代从最小子问题开始，渐渐解决更大的子问题，直到得到最终结果。
动态规划的三大特点
- 最优子结构：问题的最优解可以通过子问题的最优解来构造。例如，最长公共子序列问题的最优解可以通过子问题的解来构造。
- 重叠子问题：不同的子问题可能会多次出现，因此可以通过记忆化来存储已解决的子问题，制止重复盘算。
- 状态转移：通过当前状态和已解决的子问题来推导出下一个状态。
动态规划的经典问题
1. 0/1 背包问题
问题形貌：
- 有一个背包，最多可以容纳重量为 W 的物品。
- 有 n 个物品，每个物品的重量是 w，代价是 v。
- 问：怎样选择物品，使得背包的总代价最大，且总重量不凌驾 W？
动态规划解法：
- 界说状态 dp[j]：表现前 i 个物品，背包容量为 j 时的最大代价。
- 状态转移方程：
- 如果不选择第 i 个物品：dp[j] = dp[i-1][j]
- 如果选择第 i 个物品：dp[j] = dp[i-1][j-w] + v
- 最终的状态转移方程为：dp[j] = max(dp[i-1][j], dp[i-1][j-w] + v)
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- int knapsack(int W, vector<int>& w, vector<int>& v, int n) {
- // dp[i][j]表示前i个物品，容量为j时的最大价值
- vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= W; j++) {
- if (w[i - 1] <= j) {
- // 当前物品不放入或放入两种选择的最大值
- dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
- } else {
- dp[i][j] = dp[i - 1][j]; // 当前物品不能放入
- }
- }
- }
- return dp[n][W]; // 返回最大价值
- }
- int main() {
- int W = 10; // 背包容量
- vector<int> w = {2, 3, 4, 5}; // 物品重量
- vector<int> v = {3, 4, 5, 6}; // 物品价值
- int n = w.size();
- cout << "Max value in knapsack: " << knapsack(W, w, v, n) << endl;
- return 0;
- }
2. 最长公共子序列问题
问题形貌：
- 给定两个字符串 s1 和 s2，求它们的最长公共子序列（LCS）。
动态规划解法：
- 界说状态 dp[j]：表现 s1[0...i-1] 和 s2[0...j-1] 的最长公共子序列长度。
- 状态转移方程：
- 如果 s1[i-1] == s2[j-1]，那么 dp[j] = dp[i-1][j-1] + 1
- 否则，dp[j] = max(dp[i-1][j], dp[j-1])
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- int longestCommonSubsequence(string s1, string s2) {
- int m = s1.size(), n = s2.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 (s1[i - 1] == s2[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() {
- string s1 = "abcde";
- string s2 = "ace";
- cout << "Length of Longest Common Subsequence: " << longestCommonSubsequence(s1, s2) << endl;
- return 0;
- }
- Length of Longest Common Subsequence: 3
斐波那契数列是经典的动态规划问题。其界说是：
- F(0) = 0
- F(1) = 1
- F(n) = F(n-1) + F(n-2)
动态规划解法通过迭代制止了递归中的重复盘算。
- #include <iostream>
- using namespace std;
- int fib(int n) {
- if (n <= 1) return n;
-
- int prev2 = 0, prev1 = 1;
- for (int i = 2; i <= n; i++) {
- int curr = prev1 + prev2;
- prev2 = prev1;
- prev1 = curr;
- }
- return prev1;
- }
- int main() {
- int n = 10;
- cout << "Fibonacci of " << n << " is " << fib(n) << endl;
- return 0;
- }
总结
动态规划是一种通过将问题分解成小问题并利用已解决的小问题来制止重复盘算的技术。其核心思想是利用状态表现问题的不同阶段，并通过状态转移方程来递推求解。在实际应用中，动态规划非常实用于具有“最优子结构”和“重叠子问题”特性的问题，常见的问题有背包问题、最长公共子序列、矩阵链乘法等。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
