动态规划解题思路与常见题型总结
系统讲解动态规划解题五步法:确定状态表示、状态转移方程、初始化、填表顺序及返回值。涵盖路径问题、多状态 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