动态规划

动态规划（Dynamic Programming，简称 DP）是一种常用于优化问题的算法。它解决的问题通常具有重叠子问题和最优子结构性质，可以通过将问题分解成相互依赖的子问题来求解整个问题的最优解。
动态规划算法主要分为以下几个步骤：

1. 定义状态：将问题描述成一个状态模型，包括状态变量和状态转移方程。
2. 初始化：将状态模型中的变量初始化为特定的值。
3. 状态转移：根据状态转移方程，通过之前的状态计算当前状态的值。
4. 计算最优解：通过计算得到最终的最优解。

动态规划算法的优点在于它可以避免重复计算，因此在处理复杂的问题时特别有用。然而，它的缺点在于，由于需要存储中间结果，它可能需要更多的空间来存储数据。

动态规划经典问题

以下是一些经典的动态规划问题：

1. 最长公共子序列（LCS）：给定两个字符串，求它们的最长公共子序列。
2. 最长递增子序列（LIS）：给定一个序列，求它的最长递增子序列。
3. 背包问题：给定一个背包和一组物品，每个物品有重量和价值，求在不超过背包容量的情况下，能够获得的最大价值。

最长公共子序列（LCS）

最长公共子序列（LCS）问题是求解两个序列的最长公共子序列，即两个序列中都出现的最长的子序列。下面介绍一种常见的基于动态规划算法的求解方法：

令 m 和 n 分别为两个序列的长度，令 c[i][j] 表示第一个序列前 i 个元素和第二个序列前 j 个元素的 LCS 的长度，则有以下状态转移方程：

c[i][j] = c[i-1][j-1] + 1 (当第一个序列的第 i 个元素等于第二个序列的第 j 个元素时)
c[i][j] = max(c[i-1][j], c[i][j-1]) (当第一个序列的第 i 个元素不等于第二个序列的第 j 个元素时)

可以看出，当两个序列的当前元素相同时，LCS 长度加 1，否则 LCS 长度不变。因此，可以根据这个状态转移方程填充整个 c 数组。

最终，LCS 的长度即为 c[m][n]，而具体的 LCS 可以通过反向追溯 c 数组得到。具体地，从 c[m][n] 开始，如果 c[i][j] 等于 c[i-1][j-1] + 1，则说明第一个序列中第 i 个元素和第二个序列中第 j 个元素都是 LCS 的元素之一，将它们加入 LCS 中；否则，根据 c[i][j] 是否等于 c[i-1][j] 或 c[i][j-1] 确定向左或向上移动。

这个算法的时间和空间复杂度均为 O(mn)。

以下是基于动态规划算法的最长公共子序列（LCS）问题的 C++ 代码实现：

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;int lcs(string s1, string s2) {int m = s1.length(), n = s2.length();int c[m+1][n+1];for (int i = 0; i <= m; i++)c[i][0] = 0;for (int i = 0; i <= n; i++)c[0][i] = 0;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (s1[i-1] == s2[j-1])c[i][j] = c[i-1][j-1] + 1;elsec[i][j] = max(c[i-1][j], c[i][j-1]);}}return c[m][n];
}int main() {string s1 = "AGGTAB";string s2 = "GXTXAYB";cout << "LCS length: " << lcs(s1, s2) << endl;return 0;
}

运行结果为：

LCS length: 4

说明 “GTAB” 是两个序列的最长公共子序列。

最长递增子序列（LIS）

最长递增子序列（Longest Increasing Subsequence，LIS）问题是一个经典的动态规划问题。下面是具体的解法及C++代码实现。

一、解法

设dp[i]为以第i个元素为结尾的最长递增子序列的长度。dp[i]的值为前i-1个数中，所有比第i个数小的数的dp值加1的最大值。

以一个序列 { 5，3，4，8，6，7 }为例：

• dp[1] = 1；（序列：5）
• dp[2] = 1；（序列：3）
• dp[3] = 2；（序列：3，4）
• dp[4] = 3；（序列：3，4，8）
• dp[5] = 3；（序列：3，4，6）
• dp[6] = 4；（序列：3，4，6，7）

二、C++代码

#include <iostream>
#include <vector>
using namespace std;int lengthOfLIS(vector<int>& nums) {if (nums.empty()) return 0;int n = nums.size();vector<int> dp(n, 1); // 其中dp[i]表示以i结尾的最长递增子序列的长度，初始值都为1int res = 1;for (int i = 1; i < n; i++) { // 遍历到ifor (int j = 0; j < i; j++) { // 遍历到i之前的每个数if (nums[j] < nums[i]) {dp[i] = max(dp[i], dp[j]+1); // 更新最长递增子序列的长度}}res = max(res, dp[i]); // 更新最长递增子序列的长度的最大值}return res;
}int main() {vector<int> nums = {5, 3, 4, 8, 6, 7};cout << lengthOfLIS(nums) << endl; // 输出4return 0;
}

上述代码中使用了vector容器，可以方便的实现动态数组。

背包问题

一、01背包问题

给定n个物品和一个容量为W的背包，物品i的重量为wt[i]，价值为val[i]。现在要求选若干件物品放入背包，使得放入的物品总重量不超过W，且价值最大。

01背包问题需要使用动态规划求解。设dp[i][j]表示前i个物品中，在总重量不超过j的情况下的最大价值。则有以下状态转移方程：

• 如果当前选的物品重量大于当前背包总重量，则不能选这个物品：dp[i][j] = dp[i-1][j]

• 否则，可以选或不选这个物品，取决于是否可以使总价值更大：

  a. 选这个物品，总重量为j，则总价值为dp[i-1][j-wt[i]]+val[i]

  b. 不选这个物品，则总价值为dp[i-1][j]

  最终取dp[n][W]即为所求答案。

二、完全背包问题

完全背包问题和01背包问题的区别在于，每个物品可以选择无限次。设dp[i][j]表示前i个物品中，在总重量不超过j的情况下的最大价值。则有以下状态转移方程：

• 如果当前选的物品重量大于当前背包总重量，则不能选这个物品：dp[i][j] = dp[i-1][j]

• 否则，可以选或不选这个物品，取决于是否可以使总价值更大：

  a. 选这个物品，总重量为j，则总价值为dp[i][j-wt[i]]+val[i]

  b. 不选这个物品，则总价值为dp[i-1][j]

  最终取dp[n][W]即为所求答案。

三、多重背包问题

多重背包问题和01背包问题的区别在于，每个物品的数量有限制。设dp[i][j]表示前i个物品中，在总重量不超过j的情况下的最大价值。则有以下状态转移方程：

• 如果当前选的物品重量大于当前背包总重量，则不能选这个物品：dp[i][j] = dp[i-1][j]

• 否则，可以选或不选这个物品，取决于是否可以使总价值更大：

  a. 选这个物品，总重量为j，则总价值为dp[i][j-wt[i]]+val[i]

  b. 不选这个物品，则总价值为dp[i-1][j]

  需要注意的是，在更新dp[i][j]的时候，需要使用max函数比较选或不选这个物品的价值。同时，如果每个物品的数量有限制，还需要对物品数量进行处理。最终取dp[n][W]即为所求答案。

四、C++代码

01背包问题：

#include <iostream>
#include <vector>
using namespace std;int knapsack01(int W, vector<int>& wt, vector<int>& val) {int n = wt.size();vector<vector<int>> dp(n+1, vector<int>(W+1, 0)); // 初始化为0for (int i = 1; i <= n; i++) {for (int j = 1; j <= W; j++) {if (wt[i-1] > j) { // 当前选的物品重量大于当前背包总重量，不能选这个物品dp[i][j] = dp[i-1][j];} else {dp[i][j] = max(dp[i-1][j], dp[i-1][j-wt[i-1]]+val[i-1]); // 取选或不选这个物品的最大价值}}}return dp[n][W];
}int main() {int W = 10;vector<int> wt = {2, 2, 6, 5, 4};vector<int> val = {6, 3, 5, 4, 6};cout << knapsack01(W, wt, val) << endl; // 输出15return 0;
}

完全背包问题：

#include <iostream>
#include <vector>
using namespace std;int knapsackCom(int W, vector<int>& wt, vector<int>& val) {int n = wt.size();vector<vector<int>> dp(n+1, vector<int>(W+1, 0)); // 初始化为0for (int i = 1; i <= n; i++) {for (int j = 1; j <= W; j++) {if (wt[i-1] > j) { // 当前选的物品重量大于当前背包总重量，不能选这个物品dp[i][j] = dp[i-1][j];} else {dp[i][j] = max(dp[i-1][j], dp[i][j-wt[i-1]]+val[i-1]); // 取选或不选这个物品的最大价值}}}return dp[n][W];
}int main() {int W = 10;vector<int> wt = {2, 2, 6, 5, 4};vector<int> val = {6, 3, 5, 4, 6};cout << knapsackCom(W, wt, val) << endl; // 输出24return 0;
}

多重背包问题：

#include <iostream>
#include <vector>
using namespace std;int knapsackMul(int W, vector<int>& wt, vector<int>& val, vector<int>& cnt) {int n = wt.size();vector<vector<int>> dp(n+1, vector<int>(W+1, 0)); // 初始化为0for (int i = 1; i <= n; i++) {for (int j = 1; j <= W; j++) {if (wt[i-1] > j) { // 当前选的物品重量大于当前背包总重量，不能选这个物品dp[i][j] = dp[i-1][j];} else {for (int k = 0; k <= cnt[i-1]; k++) { // 对物品数量进行处理if (k*wt[i-1] > j) break; // 超过容量，退出循环dp[i][j] = max(dp[i-1][j], dp[i-1][j-k*wt[i-1]]+k*val[i-1]); // 取选或不选这个物品的最大价值}}}}return dp[n][W];
}int main() {int W = 10;vector<int> wt = {2, 2, 6, 5, 4};vector<int> val = {6, 3, 5, 4, 6};vector<int> cnt = {2, 3, 1, 4, 3};cout << knapsackMul(W, wt, val, cnt) << endl; // 输出54return 0;
}