跳到主要内容C/C++ 动态规划实战:从打家劫舍到股票买卖的多状态 DP 解析 | 极客日志C++算法
C/C++ 动态规划实战:从打家劫舍到股票买卖的多状态 DP 解析
动态规划多状态问题核心在于定义清晰的状态及转移方程。涵盖打家劫舍系列(含环形数组)、删除并获得点数、粉刷房子及股票买卖系列(含冷冻期、手续费、K 次交易)。通过拆解选择与不选、买入与卖出等互斥状态,利用二维 DP 表或状态机模型解决复杂约束下的最优解问题。重点讲解如何从线性 DP 扩展到多状态 DP,以及如何处理边界条件与空间优化。
星辰大海21 浏览 打家劫舍
在处理涉及相邻元素不能同时选择的动态规划问题时,打家劫舍模型非常典型。核心思路是维护两个状态数组来记录每个位置的最优解。
f[i]:选择第 i 个位置时的最大价值
g[i]:不选择第 i 个位置时的最大价值
按摩师
题目描述
给定一个整数数组表示预约时长,求在不连续选择的情况下能获得的最大总时长。
分析
这是一个典型的线性 DP 问题。对于每个位置,我们面临两种决策:选或不选。
-
状态表示:
dp[i][0] (或 f[i]):选择第 i 个预约时的最大时长。
dp[i][1] (或 g[i]):不选择第 i 个预约时的最大时长。
-
状态转移方程:
- 若选择 i,则 i-1 必须不选:
f[i] = g[i-1] + nums[i]
- 若不选 i,则 i-1 可选可不选,取最大值:
g[i] = max(f[i-1], g[i-1])
-
初始化:
- 处理边界情况,当 n=0 时直接返回 0。
f[0] = nums[0], g[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);
vector<int> g(n, 0);
f[] = nums[];
( i = ; i < n; i++) {
f[i] = g[i - ] + nums[i];
g[i] = (g[i - ], f[i - ]);
}
(f[n - ], g[n - ]);
}
};
0
0
for
int
1
1
max
1
1
return
max
1
1
为了简化边界处理,也可以使用虚拟节点(多开一位空间):
class Solution {
public:
int massage(vector<int>& nums) {
int n = nums.size();
vector<int> f(n + 1, 0);
vector<int> g(n + 1, 0);
for (int i = 1; i <= n; i++) {
f[i] = g[i - 1] + nums[i - 1];
g[i] = max(g[i - 1], f[i - 1]);
}
return max(f[n], g[n]);
}
};
打家劫舍 II
房屋围成一圈,首尾相连,不能同时偷窃第一间和最后一间。
环形结构打破了线性 DP 的连续性。解决思路是将环拆成两条线:
- 不偷最后一间(范围 0 ~ n-2)
- 不偷第一间(范围 1 ~ n-1)
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 1) return nums[0];
return max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
}
private:
int robRange(const vector<int>& nums, int start, int end) {
int n = nums.size();
vector<int> f(end - start + 1, 0);
vector<int> g(end - start + 1, 0);
f[0] = nums[start];
for (int i = 1; i <= end - start; i++) {
f[i] = g[i - 1] + nums[start + i];
g[i] = max(g[i - 1], f[i - 1]);
}
return max(f[end - start], g[end - start]);
}
};
删除并获得点数
每次选择一个数字获得对应点数,但必须删除该数字的所有相邻值(x-1 和 x+1)。
这题本质是打家劫舍的变种。如果选择了数值 x,就不能选择 x-1 和 x+1。我们可以先统计每个数值的总和(例如出现多次的 x 累加),然后将其转化为'不能选择相邻索引'的问题。
- 构建新数组
arr,arr[x] 存储所有值为 x 的数字之和。
- 在
arr 上运行标准的打家劫舍逻辑。
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
const int N = 10010;
vector<int> arr(N, 0);
int valMax = 0;
for (int x : nums) {
arr[x] += x;
valMax = max(valMax, x);
}
vector<int> f(valMax + 1, 0);
vector<int> g(valMax + 1, 0);
for (int i = 1; i <= valMax; i++) {
f[i] = g[i - 1] + arr[i];
g[i] = max(g[i - 1], f[i - 1]);
}
return max(f[valMax], g[valMax]);
}
};
粉刷房子
有 n 栋房子,每栋房子可以刷红、绿、蓝三种颜色,相邻房子颜色不能相同,求最小花费。
这是二维 DP 的经典应用。状态不仅包含当前房子下标,还包含当前房子的颜色选择。
dp[i][0]:第 i 栋房子刷红色的最小花费
dp[i][1]:第 i 栋房子刷绿色的最小花费
dp[i][2]:第 i 栋房子刷蓝色的最小花费
状态转移时,当前颜色只能从前一栋房子的非当前颜色中转移而来。
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][0], dp[i - 1][1]) + costs[i - 1][2];
}
return min({dp[n][0], dp[n][1], dp[n][2]});
}
};
股票买卖系列
股票问题是多状态 DP 的高频考点,核心在于定义好每一天可能处于的状态(持有/未持有/冷冻期等)。
买卖股票的最佳时机含冷冻期
dp[i][0]:持有股票(买入状态)
dp[i][1]:不持有股票,且不在冷冻期(可交易状态)
dp[i][2]:不持有股票,且在冷冻期(刚卖出)
- 持有:前一天就持有,或者前一天可交易今天买入。
- 可交易:前一天可交易,或者前一天冷冻期结束。
- 冷冻期:前一天一定持有,今天卖出。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if (n == 0) return 0;
vector<vector<int>> dp(n, vector<int>(3));
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]);
}
};
买卖股票的最佳时机含手续费
简化为两个状态:持有 (f) 和 不持有 (g)。
f[i] = max(f[i-1], g[i-1] - price)
g[i] = max(g[i-1], f[i-1] + price - fee)
注意手续费可以在买入时扣,也可以在卖出时扣,只要保证只扣一次即可。
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int n = prices.size();
vector<int> f(n), 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];
}
};
买卖股票的最佳时机 III & IV
- III:最多完成两笔交易。
- IV:最多完成 k 笔交易。
当交易次数有限制时,状态需要增加一维表示已完成的交易次数。为了避免三维数组的复杂性,通常将'买入'和'卖出'状态拆分为两个二维数组 f[k] 和 g[k]。
f[i][j]:第 i 天,完成了 j 次交易,处于买入状态的最大利润。
g[i][j]:第 i 天,完成了 j 次交易,处于卖出状态的最大利润。
注意初始化的细节,特别是 j=0 时的买入状态应设为负无穷,表示不可能发生。
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
if (n == 0) return 0;
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(res, g[n][j]);
}
return res;
}
};
总结
多状态 DP 的核心在于拆解复杂约束下的状态空间。
- 互斥状态:如打家劫舍中的选与不选,粉刷房子中的不同颜色,通常用多个数组或二维 DP 列表示。
- 时间维度:股票问题引入了天数作为外层循环,内层根据状态转移。
- 状态拆分技巧:当状态超过三维难以管理时(如股票交易的买入/卖出/次数),可以将互斥动作(买/卖)拆分为两个二维表,降低维度复杂度。
- 边界处理:初始化时要特别注意非法状态(如未开始交易却持有股票)应设为极小值,避免干扰最大值计算。
掌握这些模式后,面对复杂的 DP 题目,只需理清状态定义和转移关系,即可逐步构建解决方案。
相关免费在线工具
- 加密/解密文本
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
- Gemini 图片去水印
基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印,支持批量处理与下载。 在线工具,Gemini 图片去水印在线工具,online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
- Markdown转HTML
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online
- HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online