C++算法
动态规划解题思路与常见题型总结
系统讲解动态规划解题五步法：确定状态表示、状态转移方程、初始化、填表顺序及返回值。涵盖路径问题、多状态 DP、子数组、子序列、回文串、双数组及背包问题（01、完全、多重、二维费用）。提供 C++ 代码示例，解析经典算法题如爬楼梯、最小花费、解码方法、最大子数组和、最长递增子序列、最长公共子序列等，帮助掌握动态规划核心思想与应用技巧。
系统讲解动态规划解题五步法：确定状态表示、状态转移方程、初始化、填表顺序及返回值。涵盖路径问题、多状态 DP、子数组、子序列、回文串、双数组及背包问题（01、完全、多重、二维费用）。提供 C++ 代码示例，解析经典算法题如爬楼梯、最小花费、解码方法、最大子数组和、最长递增子序列、最长公共子序列等，帮助掌握动态规划核心思想与应用技巧。
1、确定状态表示（最重要的一步）
用一个一维数组或者二维数组充当 dp（dynamic programming）表，想办法把 dp 表填满，表格的某个数据就是答案。要根据题目要求确定合适的 dp 表大小，确保最终答案在 dp 表内。把 dp 表的某个数据就当作状态表示（dp[i] 表示什么含义）。状态表示通常有两个思考方向：
- dp[i] 表示 i 位置为结尾（终点），从起点到 i 位置表示的什么。
- dp[i] 表示以 i 位置为开始（起点），从 i 位置到终点表示的什么。
如果 A 点影响 B 点（更新 B 点的状态需要用到 A 点），那么状态表示最好是 dp[i] 表示 i 位置为结尾。如果 B 点影响 A 点，那么状态表示最好是 dp[i] 表示 i 位置为开始。
如果从题目中分析出一个位置可能有多个状态，可以先定义一个粗略的状态（一维数组），再将这个粗略的状态进行细分，即增加一维，下标表示某种状态。
2、确定状态转移方程（最难的一步）
说白了就是想办法得到 dp[i] 等于什么。如果始终得不到状态转移方程，可能是状态定义的问题，需要重新定义状态或者细分状态。
3、初始化
这一步是为了保证填表的时候不会有越界问题。初始化的这些值要保证后面的填表是正确的。
4、确定填表顺序
这一步是为了保证在填表的时候，所需要的状态已经被填过了。要做到确定从哪里开始填以及填表的方向。如果 dp[i] 表示 i 位置为结尾，填表顺序一般是从起点到终点；如果 dp[i] 表示 i 位置为开始，填表顺序一般是从终点到起点。
5、确定返回值
根据题目要求和状态表示，确定返回值。
在原 dp 表的前面加上一个虚拟的'结点'，建立新旧 dp 表的映射关系。可以简化代码。
对于二维 dp 表，可以在原 dp 表的基础上增加一行和一列（这不是固定的，要根据题目）。
注意事项:
题目中给出起点和终点，要求算出从起点到终点有多少条不同路径，可以使用动态规划解决这类问题。这类问题通常要判断 dp[i] 表示 i 位置为结尾还是 dp[i] 表示以 i 位置为开始。
解析：将 dp[i][j] 定义为从起点到 (i, j) 位置一共有多少条不同路径。只有 (i-1, j) 或 (i, j-1) 位置可以到达 (i, j) 位置，即：dp[i][j] = dp[i-1][j] + dp[i][j-1]。
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
dp[0][1] = 1;
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m][n];
}
};
解析：这道题最重要的是想到 dp[i] 表示以 i 位置为开始（起点），从 i 位置到终点所需最少血量。
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int row = dungeon.size();
int col = dungeon[0].size();
vector<vector<int>> dp(row + 1, vector<int>(col + 1, INT_MAX));
dp[row - 1][col] = 1;
for(int i = row - 1; i >= 0; i--) {
for(int j = col - 1; j >= 0; j--) {
int minHP = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
dp[i][j] = max(1, minHP);
}
}
return dp[0][0];
}
};
之前的 DP 问题，每个位置的状态表示只有一个 dp[i]，现在尝试每个位置的状态表示有多个，可以用 f[i] 和 g[i] 表示。
解析：用 f[i] 表示：如果这个位置接，目前最长服务时长；g[i] 表示：如果这个位置不接，目前最长服务时长。 f[i] = g[i-1] + nums[i] g[i] = max(f[i-1], g[i-1]) 最后的结果就是：max(f[n-1], g[n-1])
class Solution {
public:
int massage(vector<int>& nums) {
if(nums.size() == 0) return 0;
int n = nums.size();
if(n == 1) return nums[0];
vector<int> f(n);
vector<int> g(n);
f[0] = nums[0];
g[0] = 0;
for(int i = 1; i < n; i++) {
f[i] = g[i - 1] + nums[i];
g[i] = max(f[i - 1], g[i - 1]);
}
return max(f[n - 1], g[n - 1]);
}
};
解析：对第一个位置分类讨论即可。
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.empty()) return 0;
if(nums.size() == 1) return nums[0];
int ret1 = _rob(nums, 2, nums.size() - 2) + nums[0];
int ret2 = _rob(nums, 1, nums.size() - 1);
return max(ret1, ret2);
}
int _rob(vector<int>& nums, int start, int end) {
int n = end - start + 1;
if(n <= 0) return 0;
if(n == 1) return nums[start];
vector<int> f(n);
vector<int> g(n);
f[0] = nums[start];
g[0] = 0;
for(int i = 1; i < n; i++) {
f[i] = g[i - 1] + nums[start + i];
g[i] = max(f[i - 1], g[i - 1]);
}
return max(f[n - 1], g[n - 1]);
}
};
解析：开辟一个大小为 10001 的数组 arr，arr[i] 表示 nums 数组中 i 数字的总数，只要对 arr 数组使用'按摩师'的思路即可。
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
int arr[10001] = {0};
for(auto i : nums) arr[i] += i;
int f[10001] = {0};
int g[10001] = {0};
f[0] = arr[0];
g[0] = 0;
for(int i = 1; i < 10001; i++) {
f[i] = g[i - 1] + arr[i];
g[i] = max(f[i - 1], g[i - 1]);
}
return max(f[10000], g[10000]);
}
};
解析：dp[i][0] 表示 i 位置房子涂红色，此时的最小花费。 dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i-1][0];
class Solution {
public:
int minCost(vector<vector<int>>& costs) {
int n = costs.size();
vector<vector<int>> dp(n + 1, vector<int>(3, 0));
for(int i = 1; i <= n; i++) {
dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
dp[i][2] = min(dp[i - 1][1], dp[i - 1][0]) + costs[i - 1][2];
}
return min(min(dp[n][0], dp[n][1]), dp[n][2]);
}
};
解析：dp[i][0] 表示第 i 天结束后手里没有股票，dp[i][1] 表示第 i 天结束后手里有一支股票。 dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size() == 1) return 0;
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(2));
dp[0][0] = 0;
dp[0][1] = -prices[0];
for(int i = 1; i < n; i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return max(dp[n - 1][0], dp[n - 1][1]);
}
};
解析：f[i][j] 表示第 i 天结束后，完成了 j 次交易，手里有一支股票；g[i][j] 表示第 i 天结束后，完成了 j 次交易，手里没有股票。
class Solution {
public:
const int INF = 0x3f3f3f3f;
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<int>> f(n, vector<int>(3, -INF));
vector<vector<int>> g(n, vector<int>(3, -INF));
f[0][0] = -prices[0];
g[0][0] = 0;
for(int i = 1; i < n; i++) {
for(int j = 0; j < 3; j++) {
f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
g[i][j] = g[i - 1][j];
if(j >= 1) g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
}
}
int ret = 0;
for(int i = 0; i < 3; i++) ret = max(ret, g[n - 1][i]);
return ret;
}
};
运用动态规划解决求数组的某个特定子数组。
解析：dp[i] 定义为：以 i 位置为结尾的最大连续子数组的和。 dp[i] = max(dp[i-1] + nums[i], nums[i])
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n);
dp[0] = nums[0];
int ret = nums[0];
for(int i = 1; i < n; i++) {
dp[i] = max(nums[i], nums[i] + dp[i - 1]);
if(dp[i] > ret) ret = dp[i];
}
return ret;
}
};
解析：分两种情况：1. 刚好在数组内部（同最大子数组和）；2. 数组的头部和尾部（总和减去最小子数组和）。
class Solution {
public:
int maxSubarraySumCircular(vector<int>& nums) {
int n = nums.size();
if(n == 1) return nums[0];
int sum = 0;
for(auto i : nums) sum += i;
vector<int> dp(n);
dp[0] = nums[0];
int ret1 = nums[0];
for(int i = 1; i < n; i++) {
dp[i] = max(nums[i], dp[i - 1] + nums[i]);
if(dp[i] > ret1) ret1 = dp[i];
}
int ret2 = sum - nums[0];
for(int i = 1; i < n; i++) {
dp[i] = min(nums[i], dp[i - 1] + nums[i]);
if(sum != dp[i] && sum - dp[i] > ret2) ret2 = sum - dp[i];
}
return max(ret1, ret2);
}
};
解析：dp[i] 定义为 s 的 [0, i] 子串是否可以由字典的单词拼接而成。
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int n = s.size();
unordered_set<string> hash;
for(auto& str : wordDict) hash.insert(str);
vector<bool> dp(n + 1, false);
dp[0] = true;
s = " " + s;
for(int i = 1; i <= n; i++) {
for(int j = i; j >= 1; j--) {
if(dp[j - 1] && hash.count(s.substr(j, i - j + 1))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
};
子序列 VS 子数组
**子序列：**是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序所构成的序列。 **子数组：**数组中一段连续的序列。
解析：dp[i] 表示：以 i 位置为结尾的最长递增子序列的长度。
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1);
for(int i = 1; i < n; i++) {
int m = 0;
for(int j = i - 1; j >= 0; j--) {
if(nums[j] < nums[i]) m = max(m, dp[j]);
}
dp[i] += m;
}
int ret = 1;
for(auto i : dp) ret = max(i, ret);
return ret;
}
};
解析：dp[i][j] 表示以 i 位置和 j 位置（规定 i < j) 为结尾的最长斐波那契子序列的长度。
class Solution {
public:
int lenLongestFibSubseq(vector<int>& arr) {
int n = arr.size();
map<int, int> hash;
for(int i = 0; i < n; i++) hash.insert({arr[i], i});
vector<vector<int>> dp(n, vector<int>(n, 2));
for(int i = 0; i < n - 1; i++) {
for(int j = i + 1; j < n; j++) {
int aim = arr[j] - arr[i];
if(hash.count(aim) && aim < arr[i]) dp[i][j] = dp[hash[aim]][i] + 1;
}
}
int ret = 0;
for(int i = 0; i < n - 1; i++)
for(int j = i + 1; j < n; j++)
ret = max(ret, dp[i][j]);
if(ret < 3) return 0;
return ret;
}
};
运用动态规划解决回文串问题时，一般的思路是：选取一段区间来研究问题。选取 [i, j] 区间，讨论 i 位置和 j 位置的字符是否相同来划分问题。
解析：dp[i][j] 表示：以 i 位置为开头和以 j 位置为结尾的字符串，是否是回文串。
class Solution {
public:
int countSubstrings(string s) {
int n = s.size();
vector<vector<bool>> dp(n, vector<bool>(n));
for(int i = n - 1; i >= 0; i--) {
for(int j = i; j < n; j++) {
if(s[i] != s[j]) dp[i][j] = false;
else {
if(i == j || i + 1 == j) dp[i][j] = true;
else dp[i][j] = dp[i + 1][j - 1];
}
}
}
int ret = 0;
for(int i = 0; i < n; i++)
for(int j = i; j < n; j++)
if(dp[i][j]) ret++;
return ret;
}
};
解析：dp[i] 定义为：从 0 位置到 i 位置的子串的最少分割次数。
class Solution {
public:
int minCut(string s) {
int n = s.size();
vector<vector<bool>> dp1(n, vector<bool>(n));
for(int i = n - 1; i >= 0; i--) {
for(int j = i; j < n; j++) {
if(s[i] != s[j]) dp1[i][j] = false;
else if(i == j || i + 1 == j) dp1[i][j] = true;
else dp1[i][j] = dp1[i + 1][j - 1];
}
}
vector<int> dp2(n, INT_MAX);
for(int i = 0; i < n; i++) {
if(dp1[0][i]) dp2[i] = 0;
else {
for(int j = 1; j <= i; j++) {
if(dp1[j][i]) dp2[i] = min(dp2[i], dp2[j - 1] + 1);
}
}
}
return dp2[n - 1];
}
};
解析：dp[i][j] 表示在 [i, j] 区间内所有子序列中，最长回文子序列的长度。
class Solution {
public:
int longestPalindromeSubseq(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n));
for(int i = n - 1; i >= 0; i--) {
for(int j = i; j < n; j++) {
if(s[i] == s[j]) {
if(i == j) dp[i][j] = 1;
else if(i + 1 == j) dp[i][j] = 2;
else dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
}
}
}
return dp[0][n - 1];
}
};
解析：dp[i][j] 定义为：text1 的 [0, i] 区间和 text2 的 [0, j] 区间的所有子序列中，最长公共子序列的长度。
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size();
int n = text2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
text1 = " " + text1;
text2 = " " + text2;
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
if(text1[i] == text2[j]) 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];
}
};
解析：dp[i][j] 表示：s 字符串的 [0, i] 字串是否与 p 字符串的 [0, j] 字串匹配。
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size();
int n = p.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, false));
dp[0][0] = true;
for(int i = 0; i < n; i++) {
if(p[i] == '*') dp[0][i + 1] = true;
else break;
}
s = " " + s;
p = " " + p;
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
if(p[j] == '?') dp[i][j] = dp[i - 1][j - 1];
else if(p[j] == '*') dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
else if(p[j] == s[i] && dp[i - 1][j - 1]) dp[i][j] = true;
}
}
return dp[m][n];
}
};
背包问题是⼀种组合优化的 NP 完全问题。 根据物品的个数，可以分为如下⼏类： • 01 背包问题：每个物品只有⼀个 • 完全背包问题：每个物品有⽆限多个 • 多重背包问题：每件物品最多有 si 个 • 混合背包问题：每个物品会有上⾯三种情况 • 分组背包问题：物品有 n 组，每组物品⾥有若⼲个，每组⾥最多选⼀个物品
你有一个背包，最大容量为 V。现有 n 件物品，第 i 件物品的体积为 vi，价值为 wi。
解析：dp[i][j] 定义为从第一个物品到第 i 个物品，背包容量为 j，此时的最大总价值。
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n = 0;
int max_v = 0;
cin >> n >> max_v;
vector<int> v(n + 1);
vector<int> w(n + 1);
for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
vector<int> dp(max_v + 1, 0);
for(int i = 1; i <= n; i++) {
for(int j = max_v; j >= 0; j--) {
if(j - v[i] >= 0) {
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
}
cout << dp[max_v] << endl;
return 0;
}
解析：把 nums 数组作为物品的体积，所有物品的体积之和为 sum，有一个背包的体积为 sum / 2。
class Solution {
public:
bool canPartition(vector<int>& nums) {
int n = nums.size();
int sum = 0;
for(auto i : nums) sum += i;
if(sum % 2) return false;
int max_v = sum / 2;
vector<vector<bool>> dp(n + 1, vector<bool>(max_v + 1, false));
dp[0][0] = true;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= max_v; j++) {
dp[i][j] = dp[i - 1][j] || ((j - nums[i - 1] >= 0) && dp[i - 1][j - nums[i - 1]]);
}
}
return dp[n][max_v];
}
};
你有一个背包，最多能容纳的体积是 V。现在有 n 种物品，每种物品有任意多个。
解析：dp[i][j] 表示：从前 i 种物品中选，背包最大容量为 j，此时的最大总价值。 dp[i][j] = max(dp[i-1][j], dp[i][j-v[i]] + w[i])
#include <iostream>
#include <string.h>
using namespace std;
const int N = 1010;
int v[N];
int w[N];
int n;
int V;
int dp[N][N];
int main() {
cin >> n >> V;
for(int i = 1; i <= n; i++) {
cin >> v[i] >> w[i];
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= V; j++) {
dp[i][j] = dp[i - 1][j];
if(j - v[i] >= 0) dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
}
}
cout << dp[n][V] << endl;
return 0;
}
解析：dp[i][j] 表示：从前 i 种银币中选择，是否可以刚好凑成 j，如果可以，在所有的选法中，银币最少的个数。
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int n = coins.size();
vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0));
for(int i = 1; i <= amount; i++) dp[0][i] = -1;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= amount; j++) {
dp[i][j] = dp[i - 1][j];
if(j - coins[i - 1] >= 0 && dp[i][j - coins[i - 1]] != -1) {
if(dp[i][j] == -1) dp[i][j] = dp[i][j - coins[i - 1]] + 1;
else dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1);
}
}
}
return dp[n][amount];
}
};
如果物品的数量是有限个（不全为 1），那么就是多重背包问题。
#include <iostream>
#include <unordered_set>
using namespace std;
const int N = 7;
const int M = 1010;
int a[N];
bool dp[N][M];
int w[7] = { 0, 1, 2, 3, 5, 10, 20 };
int main() {
for (int i = 1; i <= 6; i++) cin >> a[i];
for (int i = 0; i <= 6; i++) dp[i][0] = true;
for (int i = 1; i <= 6; i++) {
for (int j = 1; j < M; j++) {
for (int k = 0; k <= a[i] && (j - k * w[i] >= 0); k++) {
if (dp[i - 1][j - k * w[i]]) {
dp[i][j] = true;
break;
}
}
}
}
int ret = 0;
for (int i = 1; i < M; i++)
if (dp[6][i]) ret++;
cout << "Total=" << ret << endl;
return 0;
}
什么是二维费用的背包问题？在 01 背包中，只有一个限制条件，即背包装的物品体积不能超过背包体积，二维费用的背包问题即有两个限定条件：背包装的物品体积和重量不能超过背包体积和最大载重。
解析：dp[i][j][k] 表示：从前 i 个字符串中选择，0 不超过 j 个，1 不超过 k 个，在所有选法中的最大子集数。
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
int x = strs.size();
vector<vector<vector<int>>> dp(x + 1, vector<vector<int>>(m + 1, vector<int>(n + 1, 0)));
for(int i = 1; i <= x; i++) {
int a = 0;
int b = 0;
int cur = 0;
while(cur < strs[i - 1].size()) {
if(strs[i - 1][cur] == '0') a++;
else b++;
cur++;
}
for(int j = 0; j <= m; j++) {
for(int k = 0; k <= n; k++) {
dp[i][j][k] = dp[i - 1][j][k];
if(j >= a && k >= b) dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - a][k - b] + 1);
}
}
}
return dp[x][m][n];
}
};
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online