309.最佳买卖股票时机含冷冻期
文章讲解：代码随想录 (programmercarl.com)
题目链接：309. 最佳买卖股票时机含冷冻期 - 力扣（LeetCode）
题目：
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
分析：
-
确定dp数组以及下标的含义
dp[i] [j]，第i天状态为j，所剩的最多现金为dp[i] [j]。
- 状态一：买入股票状态（今天买入股票，或者是之前就买入了股票然后没有操作）
- 卖出股票状态，这里就有两种卖出股票状态
- 状态二：两天前就卖出了股票，度过了冷冻期，一直没操作，今天保持卖出股票状态
- 状态三：今天卖出了股票
- 状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！
j的状态为：
- 0：状态一
- 1：状态二
- 2：状态三
- 3：状态四
注意这里的每一个状态，例如状态一，是买入股票状态并不是说今天已经就买入股票，而是说保存买入股票的状态即：可能是前几天买入的，之后一直没操作，所以保持买入股票的状态。
-
确定递归公式
达到买入股票状态（状态一）即：dp[i] [0]，有两个具体操作：
- 操作一：前一天就是持有股票状态（状态一），dp[i] [0] = dp[i - 1] [0]
- 操作二：今天买入了，有两种情况
- 前一天是冷冻期（状态四），dp[i - 1] [3] - prices[i]
- 前一天是保持卖出股票状态（状态二），dp[i - 1] [1] - prices[i]
所以操作二取最大值，即：max(dp[i - 1] [3], dp[i - 1] [1]) - prices[i]
那么dp[i] [0] = max(dp[i - 1] [0], max(dp[i - 1] [3], dp[i - 1] [1]) - prices[i]);
达到保持卖出股票状态（状态二）即：dp[i] [1]，有两个具体操作：
- 操作一：前一天就是状态二
- 操作二：前一天是冷冻期（状态四）
dp[i] [1] = max(dp[i - 1] [1], dp[i - 1] [3]);
达到今天就卖出股票状态（状态三），即：dp[i] [2] ，只有一个操作：
- 操作一：昨天一定是买入股票状态（状态一），今天卖出
即：dp[i] [2] = dp[i - 1] [0] + prices[i];
达到冷冻期状态（状态四），即：dp[i] [3]，只有一个操作：
- 操作一：昨天卖出了股票（状态三）
dp[i] [3] = dp[i - 1] [2];
-
dp数组如何初始化
这里主要讨论一下第0天如何初始化。
如果是持有股票状态（状态一）那么：dp[0] [0] = -prices[0]，买入股票所剩现金为负数。
保持卖出股票状态（状态二），第0天没有卖出dp[0] [1]初始化为0就行，
今天卖出了股票（状态三），同样dp[0] [2]初始化为0，因为最少收益就是0，绝不会是负数。
同理dp[0] [3]也初始为0。
-
确定遍历顺序
从递归公式上可以看出，dp[i] 依赖于 dp[i-1]，所以是从前向后遍历。
-
举例推导dp数组
以 [1,2,3,0,2] 为例，dp数组如下：
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() == 0) return 0;
vector<vector<int>> dp(prices.size(), vector<int>(4, 0));
dp[0][0] = -prices[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][3]) - prices[i]);
dp[i][1] = 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];
}
int n = prices.size();
return max(dp[n - 1][1], max(dp[n - 1][2], dp[n - 1][3]));
}
};
714.买卖股票的最佳时机含手续费
文章讲解：代码随想录 (programmercarl.com)
题目链接：714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）
题目：
给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
分析：
这里重申一下dp数组的含义：
dp[i] [0] 表示第i天持有股票所省最多现金。 dp[i] [1] 表示第i天不持有股票所得最多现金
如果第i天持有股票即dp[i] [0]， 那么可以由两个状态推出来
- 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1] [0]
- 第i天买入股票，所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即：dp[i - 1] [1] - prices[i]
所以：dp[i] [0] = max(dp[i - 1] [0], dp[i - 1] [1] - prices[i]);
在来看看如果第i天不持有股票即dp[i] [1]的情况， 依然可以由两个状态推出来
- 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1] [1]
- 第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金，注意这里需要有手续费了即：dp[i - 1] [0] + prices[i] - fee
所以：dp[i] [1] = max(dp[i - 1] [1], dp[i - 1] [0] + prices[i] - fee);
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int n = prices.size();
if (n == 0 ) return 0;
vector<vector<int>> dp(n, vector<int>(2, 0));
dp[0][0] = -prices[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][0] + prices[i] - fee);
}
return max(dp[n - 1][0], dp[n - 1][1]);
}
};