代码随想录| 动态规划188.买卖股票的最佳时机IV 309.最佳买卖股票时机含冷冻期 714.买卖股票的最佳时机含手续费
188.买卖股票的最佳时机IV
题目
参考文章
思路：与123.买卖股票的最佳时机|||相似。
使用二维数组 dp[i][j] ：第i天的状态为j，所剩下的最大现金是dp[i][j]
j的状态表示为：
- 0 表示不操作
- 1 第一次买入
- 2 第一次卖出
- 3 第二次买入
- 4 第二次卖出
- .....
强调一下：dp[i][1]，表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票，这是很多同学容易陷入的误区。
这题这里要类比j为奇数是买，偶数是卖的状态。
大家应该发现规律了吧 ，除了0以外，偶数就是卖出，奇数就是买入。
题目要求是至多有K笔交易，那么j的范围就定义为 2 * k + 1 就可以了。
可以推出dp[0][j]当j为奇数的时候都初始化为 -prices[0]，当j为偶数时初始化为0
也可以采用三维数组的方式，[i][j][k]表示第i天第j次买卖，k为买卖状态（0，1），
初始化方式：卖出的状态仍初始化为-price[0]
核心代码如下：
for (int i = 1; i < len; i++) {
for (int j = 1; j <= k; j++) {
// dp方程, 0表示不持有/卖出, 1表示持有/买入
dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
}
}
代码：
class Solution {
//二维数组形式
public int maxProfit(int k, int[] prices) {
if(prices.length==0){
return 0;
}
int len=prices.length;
int[][] dp=new int[len][k*2+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<k*2-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];
}
}309.最佳买卖股票时机含冷冻期
题目
参考文章
思路：这里题目加了个冷冻期，所以状态会多两个，为什么会多两个呢？因为有一个是冷冻期状态，一个是保持卖出股票状态（即买入后，还没卖），这个状态本来是可以和卖出股票状态放一起的，但是冷冻期状态的时候要用到，所以要分出来。
dp[i][0] 持有股票状态（可买入，可不买入）
dp[i][1] 保持卖出股票状态（即进入冷冻期后以及买入股票之前的状态）
dp[i][2] 卖出股票状态（卖了股票）
dp[i][3] 冷冻期状态 （即买卖一次后的冷冻期状态）
递推式
dp[i][0]=max(dp[i-1][0],max(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-1][0]+prices[i]; //状态：卖出股票，即在买入股票剩余的钱+当前卖出股票所得的钱
dp[i][3]=dp[i-1][2];//状态：冷冻期即是卖出股票后的一天的钱
初始化：
dp[0][0]=-prices[0];
dp[0][1]=dp[0][2]=dp[0][3]=0;
代码：
class Solution {
public int maxProfit(int[] prices) {
int len=prices.length;
if(len==0){
return 0;
}
int[][] dp=new int[len][4];
dp[0][0]=-prices[0];
for(int i=1;i<len;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[len-1][1],Math.max(dp[len-1][2],dp[len-1][3]));
}
}714.买卖股票的最佳时机含手续费
题目
参考文章
思路：本题思路其实和 122.买卖股票的最佳时机II 一样，只是多了一个手续费，而且一次交易（即买入卖出算一次）只收一次手续费，只要减去手续费就好了。
代码：
class Solution {
public int maxProfit(int[] prices, int fee) {
int len=prices.length;
if(len==0){
return 0;
}
int[][] dp=new int[len][2];
dp[0][0]=-prices[0];
dp[0][1]=0;
for(int i=1;i<len;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 dp[len-1][1];
}
}