跳到主要内容C++ 多状态 DP 思路:打家劫舍与股票买卖 | 极客日志C++算法
C++ 多状态 DP 思路:打家劫舍与股票买卖
多状态 DP 在打家劫舍和股票问题中的应用。通过按摩师、打家劫舍 II 等题介绍互斥状态与环形拆解,粉刷房子用二维 dp 处理颜色限制;股票系列则使用状态机模型,包括冷冻期、手续费、限交易次数等变种。给出了状态定义、转移方程和 C++ 代码实现,并提醒了初始化与边界处理。
多状态 DP 思路:打家劫舍与股票买卖
动态规划里,多状态 DP 是挺常见的一类题。打家劫舍系列和股票买卖正好是练习状态拆分的好材料。下面用几道例题把常见的状态定义和转移方程过一遍。
打家劫舍系列
这类题的核心是相邻元素不能同时选,所以通常维护「选」和「不选」两个状态数组。
1. 按摩师

不能连续选择预约,求最长预约时长。
定义两个状态:
f[i]:选择第 i 个位置时的最大时长。
g[i]:不选第 i 个位置时的最大时长。
转移方程:
- 选 i 则 i-1 必须不选:
f[i] = g[i-1] + nums[i]
- 不选 i 则 i-1 可选可不选:
g[i] = max(g[i-1], f[i-1])
实现时注意边界,数组为空直接返回 0。
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[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]);
}
(f[n - ], g[n - ]);
}
};
return
max
1
1
2. 打家劫舍 II
房屋围成一圈,意味着首尾不能同时偷。把环形问题拆成两个线性情况:
- 选第一个房子,不选最后一个(范围
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) {
if (start > end) return 0;
int n = nums.size();
vector<int> f(n, 0);
vector<int> g(n, 0);
f[start] = nums[start];
for (int i = start + 1; i <= end; i++) {
f[i] = g[i - 1] + nums[i];
g[i] = max(g[i - 1], f[i - 1]);
}
return max(f[end], g[end]);
}
};
3. 删除并获得点数
选数字 x 拿 x 分,但必须删掉所有 x-1 和 x+1。这其实就是打家劫舍的变形:如果选了数值 x,就不能选 x-1 和 x+1。统计每个数值的总和,把值本身当成下标,问题就转化成了线性打家劫舍。
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
const int N = 10010;
int arr[N] = {};
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]);
}
};
4. 粉刷房子
相邻房子颜色不能相同,求最小花费。用 dp[i][color] 表示第 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][1], dp[i - 1][0]) + costs[i - 1][2];
}
return min({dp[n][0], dp[n][1], dp[n][2]});
}
};
股票买卖系列
股票问题本质是状态机模型。根据是否持有、是否处于冷冻期等来定义状态。
1. 含冷冻期
dp[i][0]:持有股票
dp[i][1]:不持有且可交易
dp[i][2]:不持有且处于冷冻期
dp[i][0] = max(dp[i-1][0], dp[i-1][1] - price)
dp[i][1] = max(dp[i-1][1], dp[i-1][2])
dp[i][2] = dp[i-1][0] + price
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]);
}
};
2. 含手续费
每次交易收取固定手续费,在卖出时扣除。状态分为持有 f[i] 和不持有 g[i]。
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];
}
};
3. 最多两笔交易 (III)
需要记录交易次数 j。状态:第 i 天,已完成 j 次交易,当前持有/未持有。为避免三维数组,用 f[i][j] 表示持有,g[i][j] 表示未持有。
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(res, g[n][j]);
}
return res;
}
};
4. 最多 k 笔交易 (IV)
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(res, g[n][j]);
}
return res;
}
};
多状态 DP 的关键是找准状态维度以及它们之间的转移关系。像打家劫舍那样简单互斥,可以用两个数组;颜色限制则增加颜色维度;股票问题则要根据买卖、冷冻等画状态机,再落地成方程。初始化和边界处理很容易出错,特别是像 III/IV 中负无穷的初始值,写的时候要小心。
相关免费在线工具
- 加密/解密文本
使用加密算法(如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