打家劫舍
常见的思考是否使用打家劫舍问题时，遇见相邻问题不能选择此时就能思考是不是要使用打家劫舍。打家劫舍常使用两个 DP 表进行存储情况：
C++算法
C/C++ 算法入门：多状态动态规划与打家劫舍股票问题
多状态动态规划适用于处理具有互斥约束的线性序列问题。文章涵盖打家劫舍系列及粉刷房子问题，演示如何通过双状态数组推导转移方程。延伸至股票买卖场景，解析冷冻期、手续费及交易次数限制下的状态机设计，利用买入卖出分离策略降低维度，最终实现最大利润或最小成本的计算。
多状态动态规划适用于处理具有互斥约束的线性序列问题。文章涵盖打家劫舍系列及粉刷房子问题，演示如何通过双状态数组推导转移方程。延伸至股票买卖场景，解析冷冻期、手续费及交易次数限制下的状态机设计，利用买入卖出分离策略降低维度，最终实现最大利润或最小成本的计算。
常见的思考是否使用打家劫舍问题时，遇见相邻问题不能选择此时就能思考是不是要使用打家劫舍。打家劫舍常使用两个 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(f[i-1], g[i-1])初始化（回顾初始化的目的：保证填表不越界）
f[i-1] & g[i-1]，所以初始化 f[0] & g[0]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(g[n-1], f[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));
}
private:
int robRange(int l, int r, const vector<int>& nums) {
if (l > r) return 0;
int n = nums.size();
vector<int> f(n);
vector<int> g(n);
f[l] = nums[l];
for (int i = l + 1; i <= r; i++) {
f[i] = g[i-1] + nums[i];
g[i] = max(f[i-1], g[i-1]);
}
return max(f[r], g[r]);
}
};
当选择 5 后就会删除其 5-1=4 和 5+1=6 的数。
本题体现了画图的重要性，当你画图分析后，你就能一定的看出打家劫舍的影子！
解题思路：通过新增一个数组，将出现的情况都存到这些数组中，然后在这个数组中进行一个打家劫舍问题的分析，最终就得到了答案。
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]);
}
};
相邻房子的颜色不能相同，要求的是在上述条件下的最低花费成本。
对于题目给的二维数组的含义是：
状态表示：
dp[i][0]：分刷到 i 位置的时候，最后一个位置刷上了红色，此时的最小花费dp[i][1]：蓝色dp[i][2]：绿色状态转移方程：
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]初始化：添加一个虚拟节点，让原本要初始化的值放入填表过程中。
返回值：最后一个位置的最小值。
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 问题了，不再是打家劫舍而是股票问题，这类问题也就是经典的多状态问题。
交易次数无限，但卖出后需要冷冻期。
状态表示：
dp[i][0]：第 i 天结束之后，处于'买入'状态，此时的最大利润dp[i][1]：第 i 天结束之后，处于'可交易'状态，此时的最大利润dp[i][2]：第 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]初始化：
dp[0][0] = -prices[0]dp[0][1] = 0dp[0][2] = 0返回值：max(dp[n-1][1], dp[n-1][2])
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
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[i]：第 i 天结束之后，处于'买入'状态，此时的最大利润g[i]：第 i 天结束之后，处于'卖出'状态，此时的最大利润状态转移方程：
f[i] = max(f[i-1], g[i-1] - prices[i])g[i] = max(g[i-1], f[i-1] + prices[i] - fee)初始化：
f[0] = -prices[0]g[0] = 0返回值：g[n-1]
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];
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];
}
};
最多只能完成两笔交易。
状态表示：
f[i][j]：第 i 天结束之后，完成了 j 次交易，此时处于'买入'状态下的最大利润g[i][j]：第 i 天结束之后，完成了 j 次交易，此时处于'卖出'状态下的最大利润状态转移方程：
f[i][j] = max(f[i-1][j], g[i-1][j] - prices[i])g[i][j] = max(g[i-1][j], f[i-1][j-1] + prices[i])初始化：
g[0][0] = 0返回值：g[n][0~2] 中的最大值
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;
}
};
本题本质和上一题几乎完全一样，只需将交易次数 k 作为参数传入。
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;
}
};
通过上述多状态问题包含打家劫舍和股票问题后，这里进行一定性的总结帮助大家复习和回顾：
dp[i][j] 在列中通过 3 个位置分别表示红蓝绿，也为后续的股票问题进行了铺垫。f[i][j]：第 i 天结束之后，完成了 j 次交易，此时处于'买入'状态下的最大利润。当得出了状态表示后，进行分析状态得出状态转移方程，通过将状态一一列出来进行分析，它们相互的关系。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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