第九章 动态规划part09
188.买卖股票的最佳时机IV
本题是123.买卖股票的最佳时机III 的进阶版
文章讲解
思路
- 确定dp数组以及下标的含义
在动态规划：123.买卖股票的最佳时机III (opens new window)中
，使用二维数组 dp[i][j] ：第i天的状态为j，所剩下的最大现金是dp[i][j]，实际上除了0以外，j的状态表示偶数就是卖出，奇数就是买入。本题也可以用二维数组表示，题目要求是至多有K笔交易，那么j的范围就定义为 2 * k + 1 就可以了。只是奇数代表买入，偶数代表卖出。 - 确定递推公式
-
达到dp[i][1]状态，有两个具体操作：
- 操作一：第i天买入股票了，那么dp[i][1] = dp[i - 1][0] - prices[i]
- 操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][1]
- 选最大的，所以
dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]); -
同理dp[i][2]也有两个操作：
- 操作一：第i天卖出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]
- 操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2] = dp[i - 1][2]
- 所以
dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2]) - 同理可以类比剩下的状态，代码如下：
for (int j = 0; j < 2 * k - 1; j += 2) {
dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}
最大的区别就是这里要类比j为奇数是买，偶数是卖的状态。
- dp数组如何初始化
- 第0天没有操作，这个最容易想到，就是0，即：dp[0][0] = 0;
- 第0天做第一次买入的操作，dp[0][1] = -prices[0];
- 第0天做第一次卖出的操作，可以理解为当天买入，当天卖出，所以dp[0][2] = 0;
- 第0天第二次买入操作：第二次买入依赖于第一次卖出的状态，其实相当于第0天第一次买入了，第一次卖出了，然后在买入一次（第二次买入），那么现在手头上没有现金，只要买入，现金就做相应的减少。
所以第二次买入操作，初始化为：dp[0][3] = -prices[0]; - 第二次卖出初始化dp[0][4] = 0;
所以同理可以推出dp[0][j]当j为奇数的时候都初始化为 -prices[0]
以此分别类比奇偶天数的状态
for (int j = 1; j < 2 * k; j += 2) {
dp[0][j] = -prices[0];
}
确定遍历顺序
从递归公式其实已经可以看出，一定是从前向后遍历，因为dp[i]，依靠dp[i - 1]的数值。-
举例推导dp数组
以输入[1,2,3,4,5]，k=2为例。
image.png
class Solution {
public int maxProfit(int k, int[] prices) {
if(prices.length == 0) return 0;
int len = prices.length;
// [天数][股票状态]
// 股票状态: 奇数表示第 k 次交易持有, 偶数表示第 k 次交易不持有, 0 表示没有操作
int[][] dp = new int[len][2 * k + 1];
for(int i = 1; i < k * 2; i += 2){
dp[0][i] = - prices[0];
}
for(int i = 1; i < len; i++){
for(int j = 0; j <= 2 * k - 1; j += 2){
dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
dp[i][j + 2] = Math.max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}
}
return dp[len - 1][k * 2];
}
}
- 为什么在 for (int j = 0; j < k*2 - 1; j += 2) 中， j < k*2 - 1
在for (int j = 0; j < k*2 - 1; j += 2)循环中，j的上限是k*2 - 1
假设k是允许的最大交易次数： -
k * 2是我们需要考虑的所有状态的总数，因为每次交易包含买入和卖出两个状态。 -
k * 2 - 1是j的最大有效值，因为j达到k * 2时已经是一个完整交易的结束状态。
在 for 循环中：
-
j的起点是0，这表示没有进行任何操作的状态。 -
j每次增加2，确保我们只在需要更新交易状态的位置进行操作（即处理买入或卖出的状态）。
具体解释代码中的循环：
for (int j = 0; j < k*2 - 1; j += 2) {
// 更新买入状态: 第 j / 2 + 1 次交易买入的最大利润
dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
// 更新卖出状态: 第 j / 2 + 1 次交易卖出的最大利润
dp[i][j + 2] = Math.max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}
-
j + 1更新的是买入状态。 -
j + 2更新的是卖出状态。
由于 j 的最大值为 k * 2 - 1，所以 j + 1 的最大值为 k * 2 - 1（代表第 k 次交易的买入状态），而 j + 2 的最大值为 k * 2（代表第 k 次交易的卖出状态）。
这就是为什么 for 循环中的 j 条件是 j < k * 2 - 1 的原因。
309.最佳买卖股票时机含冷冻期
本题加了一个冷冻期，状态就多了，有点难度，大家要把各个状态分清，思路才能清晰
文章讲解
思路
具体可以区分出如下四个状态：
- 状态一：持有股票状态（今天买入股票，或者是之前就买入了股票然后没有操作，一直持有）
- 不持有股票状态，这里就有两种卖出股票状态
- 状态二：保持卖出股票的状态（两天前就卖出了股票，度过一天冷冻期。或者是前一天就是卖出股票状态，一直没操作）
- 状态三：今天卖出股票
- 状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！
确定dp数组以及下标的含义
dp[i][j]，第i天状态为j，所剩的最多现金为dp[i][j]。确定递推公式
达到买入股票状态（状态一）即：dp[i][0]，有两个具体操作：
- 操作一：前一天就是持有股票状态（状态一），dp[i][0] = dp[i - 1][0]
- 操作二：今天买入了，有两种情况
- 前一天是冷冻期（状态四），dp[i - 1][3] - prices[i]
- 前一天是保持卖出股票的状态（状态二），dp[i - 1][1] - prices[i]
那么dp[i][0] = max(dp[i - 1][0], dp[i - 1][3] - prices[i], 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[i][0] = Math.max(dp[i-1][0], 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] = Math.max(dp[i-1][0] + prices[i]);
dp[i][3] = dp[i-1][2];
- dp数组如何初始化
这里主要讨论一下第0天如何初始化。
如果是持有股票状态（状态一）那么：dp[0][0] = -prices[0]，一定是当天买入股票。
保持卖出股票状态（状态二），这里其实从 「状态二」的定义来说 ，很难明确应该初始多少，这种情况我们就看递推公式需要我们给他初始成什么数值。
如果i为1，第1天买入股票，那么递归公式中需要计算 dp[i - 1][1] - prices[i] ，即 dp[0][1] - prices[1]，那么大家感受一下 dp[0][1] （即第0天的状态二）应该初始成多少，只能初始为0。想一想如果初始为其他数值，是我们第1天买入股票后 手里还剩的现金数量是不是就不对了。
今天卖出了股票（状态三），同上分析，dp[0][2]初始化为0，dp[0][3]也初始为0。
确定遍历顺序
从递归公式上可以看出，dp[i] 依赖于 dp[i-1]，所以是从前向后遍历。-
举例推导dp数组
以 [1,2,3,0,2] 为例，dp数组如下：
image.png
class Solution {
public int maxProfit(int[] prices) {
if(prices == null) return 0;
int len = prices.length;
int[][] dp = new int[len][4];
/**
1. [i][0] holding the stock
2. [i][1] after cooldown but stil not buing the stock
3. [i][2] selling the stock
4. [i][3] cooldown
*/
dp[0][0] = -prices[0];
for(int i = 1; i < len; i++){
dp[i][0] = Math.max(Math.max(dp[i-1][0], 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[len-1][3], Math.max(dp[len-1][1], dp[len-1][2]));
}
}
714.买卖股票的最佳时机含手续费
相对122.买卖股票的最佳时机II ，本题只需要在计算卖出操作的时候减去手续费就可以了，代码几乎是一样的，可以尝试自己做一做。
文章讲解
思路
相对于 122.买卖股票的最佳时机II，本题只需要在计算卖出操作的时候减去手续费就可以了，代码几乎是一样的。
唯一差别在于递推公式
- 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(int[] prices, int fee) {
int[] dp = new int[2];
// 0代表持有，1代表卖出
dp[0] = -prices[0];
dp[1] = 0;
for(int i = 1; i <= prices.length; i++){
//因为循环是从1到len，所以实际上i=1，访问的是prices[0],所以为了保证数组索引对齐，这里面都是prices[i-1]
//区别于二维数组的解法，因为二维数组的循环是从1到len-1，使用i访问prices[i]
//第i-1天（这时候是用dp[0]保存的）就持有; 或第i天买入股票，所得现金就是昨天不持有股票的所得现金减去 今天的股票价格
dp[0] = Math.max(dp[0], dp[1] - prices[i - 1]);
//第i-1天就不持有；或第i天卖出股票，所得现金就是按照今天股票价格卖出再减去手续费后所得现金
dp[1] = Math.max(dp[1], dp[0] + prices[i - 1] - fee);
}
return dp[1]; //二维数组应该返回length-1，但是这里改了for循环里 i <= prices.length
}
}
股票总结
股票问题做一个总结吧
