代码随想录算法训练营第五十一天|309.最佳买卖股票时机含冷冻期 、714.买卖股票的最佳时机含手续费
最佳买卖股票时机含冷冻期
309.最佳买卖股票时机含冷冻期
文章讲解：https://programmercarl.com/0309.%E6%9C%80%E4%BD%B3%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E6%97%B6%E6%9C%BA%E5%90%AB%E5%86%B7%E5%86%BB%E6%9C%9F.html
题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/
视频讲解：https://www.bilibili.com/video/BV1rP4y1D7ku/
自己看到题目的第一想法
没想到好的处理方式。
看完代码随想录之后的想法
将当前的状态做了下拆分，整体区分出了四个状态：
- 状态一：持有状态（今天买入，或者之前就买入了一直没操作，一直持有）
- 不持有股票状态，这里有两种卖出股票状态
- 状态二：保持卖出状态（两天前就卖出，度过一天冷冻期。或者是前一天就是卖出状态，一直没操作）
- 状态三：今天卖出股票
- 状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天。
j的状态为：
0：状态一
1：状态二
2：状态三
3：状态四
自己实现过程中遇到哪些困难
看着状态转移图写的代码，但是最后返回最大值那边处理错误了，返回最大值应该是从dp[i][1-3]中取一个最大的。
还有就是Math.max最大值只能2个2个比较。
状态三和状态四不用取最大值，因为只有一个值的选择。
最终代码：
public int maxProfit(int[] prices) {
// 确定dp数组以及下标定义，第i天最大价值
// 确定递推公式：分四种情况，按照状态图处理
// 1. 达到买入股票状态（状态一）之前就买入，之前是冷冻状态然后买入，之前是卖出状态再买入
// dp[i][0] = Math.max(dp[i-1][0],dp[i-1][3]-prices[i],dp[i-1][1]-prices[i]);
// 2. 达到保持卖出股票状态（状态二）之前就卖出，之前是冷冻状态
// dp[i][1] = Math.max(dp[i-1][1],dp[i-1][3]);
// 3. 达到今天就卖出股票状态（状态三）昨天买入今天卖出，
// dp[i][2] = Math.max(dp[i-1][0] + prices[i]);
// 4. 达到冷冻期状态（状态四）
// dp[i][3] = Math.max(dp[i-1][2])
int[][] dp = new int[prices.length][4];
// 确定初始化值,第0天，只有当天买入
dp[0][0] -= prices[0];
dp[0][1] = 0;
dp[0][2] = 0;
dp[0][3] = 0;
for(int i = 1; i < prices.length; i++){
dp[i][0] = Math.max(dp[i-1][0],Math.max(dp[i-1][3]-prices[i],dp[i-1][1]-prices[i]));
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][3]);
dp[i][2] = dp[i-1][0] + prices[i];
dp[i][3] = dp[i-1][2];
}
return Math.max(dp[prices.length - 1][1],Math.max(dp[prices.length - 1][3],dp[prices.length - 1][2]));
}
买卖股票的最佳时机含手续费
714.买卖股票的最佳时机含手续费
文章讲解：https://programmercarl.com/0714.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BA%E5%90%AB%E6%89%8B%E7%BB%AD%E8%B4%B9%EF%BC%88%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%EF%BC%89.html
题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
视频讲解：https://www.bilibili.com/video/BV1z44y1Z7UR/
自己看到题目的第一想法
看完代码随想录之后的想法
和之前的题目一样，只是在不持有状态的当天卖出再减去fee。
自己实现过程中遇到哪些困难
持有状态时的第二种情况，要用前一天不持有，前一天不持有是dp[i-1][1]，而不是dp[i-1][0]，同理当天要做操作时要关注到前一天的状态，用前一天的状态的值去推导。
public int maxProfit(int[] prices, int fee) {
// 找出所有状态，状态其实和之前的一样，也只有持有和不持有
// dp数组定义，第i天的持有/不持有状态下的最大手续费。
int[][] dp = new int[prices.length][2];
// 确定递推公式
// 持有状态，不持有状态
// 持有状态：一、前一天就持有 dp[i][0] = dp[i-1][0]； 二、前一天不持有，今天持有dp[i][0] = dp[i-1][1]- prices[i];
// 不持有状态： 一、前一天不持有 dp[i][1] = dp[i-1][1]；二、前一天持有今天卖出dp[i][1] = dp[i-1][1] + prices[i] - fee;
dp[0][0] -= prices[0];
for(int i = 1; i < prices.length; i++){
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]- prices[i]);
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0] + prices[i] - fee);
}
return Math.max(dp[prices.length - 1][1],dp[prices.length - 1][0]);
}
今日收获&学习时长
进一步深化了买卖股票题目的处理方式，整体就是按照状态去散列推导公式。
