【动态规划】简单多状态（二）

📝前言说明：

本专栏主要记录本人的基础算法学习以及LeetCode刷题记录，按专题划分
每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页愚润泽

你可以点击下方链接，进行不同专题的动态规划的学习

点击链接	开始学习
斐波那契数列模型	路径问题
简单多状态（一）	简单多状态（二）
子数组系列（一）	子数组系列（二）
子序列问题（一）	子序列问题（二）
回文串问题	两个数组dp问题（一）
两个数组的dp问题（二）	01背包问题
完全背包	二维的背包问题
其他

题目

309. 买卖股票的最佳时机含冷冻期
- 优质解
714. 买卖股票的最佳时机含手续费
- 个人解
123. 买卖股票的最佳时机 III
- 优质解
188. 买卖股票的最佳时机 IV
- 个人解

309. 买卖股票的最佳时机含冷冻期

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/
在这里插入图片描述

优质解

思路：

本题的三状态怎么来的，本来是买（已卖） / 卖，但是本题多了一个冷冻期，限制的是当天买的行为，所以变成了三状态。已卖 + 可买 / 已卖 + 不可买 / 卖
dp[i]：当天结束时，最大收益。当天结束后的状态又可以再细分（开 3 * n的数组）。
- 持股dp[0]
- dp[1]不持股且明天不可以买
- dp[2]不持股且明天可以买
状态转移方程（当天结束的状态：由前一天状态和当天行为决定）：
- 可变成持股状态的：
  - 前一天不持股且明天可以买 + 当天买入；
  - 前一天持股 + 当天不变
- 可变成不持股且明天不可买的：
  - 前一天持股 + 当天卖出
- 可变成不持股且明天可买的：
  - 前一天不持股且明天可买 + 当天不变；
  - 前一天不持股且明天不可买 + 当天不变
由上可推出方程
dp[0][i] = max(dp[2][i - 1] - price[i], dp[0][i - 1])
dp[1][i] = dp[0][i - 1] + price[i]
dp[2][i] = max(dp[1][i - 1], dp[2][i - 1])
初始化：dp[0][0] = -price[0]，dp[1][0] = dp[2][0] = 0
填表顺序：三个一起填
返回值：max(dp[1][n - 1], dp[2][n - 1])

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size(); vector<vector<int>> dp(3, vector(n, 0));dp[0][0] = -prices[0];for(int i = 1; i < n; i++){dp[0][i] = max(dp[2][i - 1] - prices[i], dp[0][i - 1]);dp[1][i] = dp[0][i - 1] + prices[i];dp[2][i] = max(dp[1][i - 1], dp[2][i - 1]);}return max(dp[1][n - 1], dp[2][n - 1]);}
};

时间复杂度：O(n)
空间复杂度：O(n)

714. 买卖股票的最佳时机含手续费

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/
在这里插入图片描述

个人解

思路：

// dp[0][i] 第 i 天结束后为持股状态时的最大收益
// dp[1][i] 第 i 天结束后为不持股状态时的最大收益
// dp[0][i] = max(dp[1][i - 1] - prices[i] - fee, dp[0][i - 1]);
// dp[1][i] = max(dp[1][i - 1], dp[0][i - 1] + prices[i]);

不多说了，难度不如上一题
用时：10:00
屎山代码：

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int n = prices.size();vector<vector<int>> dp(2, vector(n, 0));dp[0][0] = -prices[0] - fee; // 让买入算手续费for(int i = 1; i < n; i++){dp[0][i] = max(dp[1][i - 1] - prices[i] - fee, dp[0][i - 1]);dp[1][i] = max(dp[1][i - 1], dp[0][i - 1] + prices[i]);}return dp[1][n - 1];}
};

时间复杂度：O(n)
空间复杂度：O(n)

123. 买卖股票的最佳时机 III

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/
在这里插入图片描述

优质解

思路：

通过分析状态表示，我们发现必须要三维才能够很好的表示状态
第一维：持股 / 不持股，第二维：最大利润，第三维：所剩交易次数

但是我们也可以把持股和不持股分出来：

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])

初始化（其实是解决越界行为）：

初始时，交易次数为 1 和 2 的初始化
- 我们可以让f[0][1] = f[0][2] = - INT_MAX / 2，即：取最小值（比所有可能的结果都小），使得该位置不会被下一天max选到，从而不影响正常的状态转移（g同理）
- /2的原因：因为g[i - 1][j] - prices[i]会导致负数溢出，所以控制一下
f[i - 1][j - 1] + prices[i]的操作：j - 1会越界
- 而这个式子中j等于0是无意义的，因为如果当天有卖出行为，则g[i][j]的j一定 >= 1
- 因此，我们可以把式子变换成：

g[i][j] = g[i - 1][j];
if(j > 1)g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);

是从第1天开始填的，基于第0天，所以：f[0][0] = -p[0]、g[0][0] = 0

代码：

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();vector<vector<int>> f(n, vector<int>(3, -INT_MAX / 2));auto g = f;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 - 1][j], f[i - 1][j - 1] + prices[i]);}}return max(max(g[n - 1][0], g[n - 1][1]), g[n - 1][2]);}
};

时间复杂度：O(n)
空间复杂度：O(n)

188. 买卖股票的最佳时机 IV

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/
在这里插入图片描述

个人解

思路：

和上一题一样

用时：6:00
屎山代码：

class Solution {
public:int maxProfit(int k, vector<int>& prices) {int n = prices.size();vector<vector<int>> f(n, vector<int>(k + 1, -INT_MAX/2));auto g = f;f[0][0] = -prices[0];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]);g[i][j] = g[i - 1][j];if(j >= 1)g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);}}int ans = 0;for(int i = 0; i <= k; i++)ans = max(ans, g[n - 1][i]);return ans;}
};