代码随想录算法训练营第四十二天 | 188.买卖股票的最佳时机IV，309.最佳买卖股票时机含冷冻期，714.买卖股票的最佳时机含手续费
训练营四十二天打卡，今天结束买票股票，冷冻期的状态定义很关键，要理解为什么要定义四个状态！
188.买卖股票的最佳时机Ⅳ
题目链接
解题过程
- 定义状态，对于每一天：
- 第
j次持有股票的最大利润 - 第
j次不持有股票的最大利润 1 <= j <= kdp[i][0]：第一次持有股票的最大利润dp[i][1]：第一次不持有股票的最大利润dp[i][3]：第二次持有股票的最大利润dp[i][4]：第二次不持有股票的最大利润- ······
- 第
动态规划
class Solution {
public:int maxProfit(int k, vector<int>& prices) {vector<vector<int>>dp(prices.size(), vector<int>(2 * k));for (int i = 0; i < 2 * k; i++) {if (i % 2 == 0) dp[0][i] = -prices[0];}for (int i = 1; i < prices.size(); i++) {dp[i][0] = max(dp[i - 1][0], -prices[i]);for (int j = 1; j < 2 * k; j++) {if (j % 2 == 1) { // 第 (j+1)/2 次不持有股票的最大利润dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);} else { // 第 (j/2)+1 次持有股票的最大利润dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);}}}return dp.back().back();}
};
309.买卖股票的最佳时机含冷冻期
题目链接
解题过程
- 定义了三个状态，但错误了，原因是要定义四个就清楚了，因为冷冻期前一天必卖出股票，所以不持有股票可以分为两种：一直不持有股票，今天卖出了股票。
- 定义四个状态：
- 状态一：持有股票
- 状态二：冷冻期
- 状态三：不持有股票且不是当天卖出
- 状态四：不持有股票且是当天卖出
- 状态转移关系
- 持有股票：
- 1.昨天持有股票，状态一
- 2.昨天是冷冻期今天买入，状态二
- 3.昨天不持有股票且昨天没有卖出股票，状态三
- 冷冻期：
- 昨天不持有股票且是当天卖出，状态四
- 不持有股票且不是当天卖出：
- 1.昨天是冷冻期，状态二
- 2.昨天不持有股票且昨天没卖出股票，状态三
- 不持有股票且是当天卖出：
- 昨天持有股票今天卖出，状态一
- 持有股票：
动态规划
class Solution {
public:int maxProfit(vector<int>& prices) {vector<vector<int>>dp(prices.size(), vector<int>(4));dp[0][0] = -prices[0]; // 持有股票最大利润dp[0][1] = 0; // 冷冻期最大利润dp[0][2] = 0; // 保持没有股票状态最大利润dp[0][3] = 0; // 今天卖出股票状态最大利润for (int i = 1; i < prices.size(); i++) {dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][1], dp[i - 1][2]) - prices[i]);dp[i][1] = dp[i - 1][3];dp[i][2] = max(dp[i - 1][1], dp[i - 1][2]);dp[i][3] = dp[i - 1][0] + prices[i];}return max(dp.back()[1], max(dp.back()[2], dp.back()[3]));}
};
714.买卖股票的最佳时机含手续费
题目链接
解题过程
- 在卖出股票时开出手续费就行，整一个过程只需要开一次手续费。
动态规划
class Solution {
public:int maxProfit(vector<int>& prices, int fee) {vector<vector<int>>dp(prices.size(), vector<int>(2));dp[0][0] = -prices[0]; // 持有股票最大利润dp[0][1] = 0; // 不持有股票最大利润for (int i = 1; i < prices.size(); 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][0] + prices[i] - fee);}return dp.back()[1];}
};