动态规划多状态问题通过定义多个状态数组来记录不同决策下的最优解。文章涵盖打家劫舍系列（含环形、删除获点、粉刷房子）及股票买卖系列（含冷冻期、手续费、交易次数限制）。核心在于状态转移方程的推导，如选择与不选择的互斥关系，以及买入卖出状态的转换。通过二维或多维 DP 表处理复杂约束，最终得出最大利润或最小成本。
本章将结合基础动态规划引入多状态问题，从简单的打家劫舍两状态 DP 到股票问题的四状态 DP，通过练代学的方式学习。
常见的思考是否使用打家劫舍问题时，遇见相邻问题不能选择此时就能思考是不是要使用打家劫舍。打家劫舍常使用两个 DP 表进行存储情况：
f[i]：选择 i 位置时的最大价值g[i]：不选择 i 位置时的最大价值不能连续的选择，求找到最长的预约时长。
dp[i]：选择到 i 位置的时候，此时的最长预约时长f[i]：选择时的最长预约g[i]：不选择时的最长时长f[i]），那么就是要加上 i-1 不选的最大值：f[i] = g[i-1] + nums[i]g[i]），那么值就是前 i-1 位置的选或者不选的最大值：g[i] = max(g[i-1], f[i-1])f[0] = nums[0]（直接填入第一个位置的时长即可）g[0] = 0（若该点不选那么就为 0）max(f[n-1], g[n-1])，最后一个位置选/不选的最大值class Solution {
public:
int massage(vector<int>& nums) {
// 不使用虚拟节点
int n = nums.size();
if (n == 0) return 0;
vector<int> f(n, 0); // 选择 i 位置
vector<int> g(n, 0); // 不选择 i 位置
f[0] = nums[0];
for (int i = 1; i < n; i++) {
f[i] = g[i - 1] + nums[i];
g[i] = max(g[i - 1], f[i - 1]);
}
return max(f[n - 1], g[n - 1]);
}
};
本题主要和上一题不同的是，收尾相连了，那么就进行特殊处理下第一个位置。 将一个线性的数组根据题意（第一个位置选 / 不选的情况）分成两份：
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 1) return nums[0];
return max(nums[0] + robRange(2, n - 2, nums), robRange(1, n - 1, nums));
}
int robRange(int start, int end, const vector<int>& nums) {
if (start > end) return 0;
int n = nums.size();
vector<int> f(n);
vector<int> g(n);
f[start] = nums[start];
for (int i = start + 1; i <= end; i++) {
f[i] = g[i - 1] + nums[i];
g[i] = max(f[i - 1], g[i - 1]);
}
return max(f[end], g[end]);
}
};
本题可以通过新增一个数组，将出现的情况都存到这些数组中，然后在这个数组中进行一个打家劫舍问题的分析。
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
int maxval = 0;
vector<int> dp(20010, 0);
for (auto v : nums) {
dp[v] += v;
maxval = max(maxval, v);
}
vector<int> f(maxval + 1);
vector<int> g(maxval + 1);
for (int i = 1; i <= maxval; i++) {
f[i] = g[i - 1] + dp[i];
g[i] = max(f[i - 1], g[i - 1]);
}
return max(f[maxval], g[maxval]);
}
};
对于题目给的二维数组的含义是：纵坐标代表房子的下标，横坐标代表颜色。其中注意的是相邻房子的颜色不能相同。要求的是在上述条件下的最低花费成本。
class Solution {
public:
int minCost(vector<vector<int>>& costs) {
int n = costs.size();
vector<vector<int>> dp(n + 1, vector<int>(3));
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 时我们可以通过多个 DP 来保存他们各自的状态，并相互的使用 DP 来算出最终答案。
下面就将继续多状态 DP 问题了，不再是打家劫舍而是股票问题，这类问题也就是经典的多状态问题。
首先肯定是以 i 位置为结尾时的最大利润，但其中它可能会有多种状态，所以就还需要 3 行来表示状态：'买入'、'可交易'、'冷冻期'。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(3));
// dp[i][0]：处于'买入'状态，此时的最大利润
// dp[i][1]：处于'可交易'状态，此时的最大利润
// dp[i][2]：处于'冷冻期'状态，此时的最大利润
dp[0][0] = -prices[0];
dp[0][1] = 0;
dp[0][2] = 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][2]);
dp[i][2] = dp[i - 1][0] + prices[i];
}
return max(dp[n - 1][1], dp[n - 1][2]);
}
};
交易次数无限，但每次都有手续费（买入和卖出只用出一次手续费）。若手里有股票就不能再买了。
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int n = prices.size();
vector<int> f(n);
vector<int> g(n);
f[0] = -prices[0];
g[0] = 0;
for (int i = 1; i < n; i++) {
f[i] = max(f[i - 1], g[i - 1] - prices[i]);
g[i] = max(g[i - 1], f[i - 1] + prices[i] - fee);
}
return g[n - 1];
}
};
最多只能完成两笔交易。只能卖了股票，才能买新股票。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<int>> f(n + 1, vector<int>(3, -0x3F3F3F3F));
vector<vector<int>> g(n + 1, vector<int>(3, -0x3F3F3F3F));
g[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= 2; j++) {
f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i - 1]);
g[i][j] = g[i - 1][j];
if (j - 1 >= 0) g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i - 1]);
}
}
int res = INT_MIN;
for (int j = 0; j <= 2; j++) {
res = max(g[n][j], res);
}
return res;
}
};
本题本质和上一题几乎完全一样。
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
vector<vector<int>> f(n + 1, vector<int>(k + 1, -0x3F3F3F3F));
vector<vector<int>> g(n + 1, vector<int>(k + 1, -0x3F3F3F3F));
g[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i - 1]);
g[i][j] = g[i - 1][j];
if (j - 1 >= 0) g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i - 1]);
}
}
int res = INT_MIN;
for (int j = 0; j <= k; j++) {
res = max(g[n][j], res);
}
return res;
}
};
通过上述多状态问题包含打家劫舍和股票问题后，这里进行一定性的总结帮助大家复习和回顾。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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