day47【代码随想录】动态规划之买卖股票的最佳时机III、买卖股票的最佳时机IV、最佳买卖股票时机含冷冻期、买卖股票的最佳时机含手续费

---

前言

1、买卖股票的最佳时机III
2、买卖股票的最佳时机IV
3、最佳买卖股票时机含冷冻期
4、买卖股票的最佳时机含手续费

---

一、买卖股票的最佳时机III（力扣123）

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
8888
分析：
与之前的区别在于最多可以买卖两次
动规五部曲
1、dp[]数组以及下标含义
dp[i][0]：不操作
dp[i][1]：第一次持有
dp[i][2]：第一次不持有
dp[i][3]：第二次持有
dp[i][4]：第二次不持有
2、递推公式
dp[i][0] = dp[i-1][0]
dp[i][1] = Math.max(dp[i-1][1],-price[i])
dp[i][2] = Math.max(dp[i-1][2],dp[i-1][1]+price[i])
dp[i][3] = Math.max(dp[i-1][3],dp[i-1][2]-price[i])
dp[i][4] = Math.max(dp[i-1][4],dp[i-1][3]+price[i])
3、初始化
dp[0][0] = 0;
dp[0][1] = -price[0];
dp[0][2] = 0;
dp[0][3] = -price[0];
dp[0][4] = 0;
4、遍历顺序
从前向后遍历，因为dp[i]，依靠dp[i - 1]的数值。

二维dp数组

class Solution {public int maxProfit(int[] prices) {int[][] dp = new int[prices.length][5];dp[0][0] = 0;dp[0][1] = -prices[0];dp[0][2] = 0;dp[0][3] = -prices[0];dp[0][4] = 0;for(int i=1;i<prices.length;i++){dp[i][1] = Math.max(dp[i-1][1],-prices[i]);dp[i][2] = Math.max(dp[i-1][2],dp[i-1][1]+prices[i]);dp[i][3] = Math.max(dp[i-1][3],dp[i-1][2]-prices[i]);dp[i][4] = Math.max(dp[i-1][4],dp[i-1][3]+prices[i]);}return dp[prices.length-1][4];}
}

优化版：（滚动数组）：

class Solution {public int maxProfit(int[] prices) {int[] dp = new int[5];dp[0] = 0;dp[1] = -prices[0];dp[2] = 0;dp[3] = -prices[0];dp[4] = 0;for(int i=1;i<prices.length;i++){dp[1] = Math.max(dp[1],-prices[i]);dp[2] = Math.max(dp[2],dp[1]+prices[i]);dp[3] = Math.max(dp[3],dp[2]-prices[i]);dp[4] = Math.max(dp[4],dp[3]+prices[i]);}return dp[4];}
}

二、买卖股票的最佳时机IV（力扣188）

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

分析：
与之前的区别在于最多可以买卖k次
根据上一题所表现出来的规律：
1、dp[]数组以及下标含义
dp[i][0]：不操作
dp[i][1]：第一次持有
dp[i][2]：第一次不持有
dp[i][3]：第二次持有
dp[i][4]：第二次不持有
……
当有k次买卖时，奇数表示买入，偶数表示卖出。
初始化

for(int j=0;j<2*k+1;j++){if(j%2==1){dp[0][j] = -prices[0];}
}

递推公式
dp[i][0] = dp[i-1][0]
dp[i][1] = Math.max(dp[i-1][1],-price[i])
dp[i][2] = Math.max(dp[i-1][2],dp[i-1][1]+price[i])
dp[i][3] = Math.max(dp[i-1][3],dp[i-1][2]-price[i])
dp[i][4] = Math.max(dp[i-1][4],dp[i-1][3]+price[i])

for(int i = 1; i<prices.length; i++){for(int j=1; j<2*k+1;j=j+2){dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-1]-prices[i]);dp[i][j+1] = Math.max(dp[i-1][j+1],dp[i-1][j]+prices[i]);}
}

class Solution {public int maxProfit(int k, int[] prices) {int[][] dp = new int[prices.length][2*k+1];for(int j=1;j<2*k+1;j++){if(j%2==1) dp[0][j] = -prices[0];}for(int i=1;i<prices.length;i++){for(int j=0;j<2*k-1;j=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[prices.length-1][2*k];}
}

三、最佳买卖股票时机含冷冻期（力扣309）

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

动规五部曲：
1、dp[]数组以及下标含义
dp[i][0]：持有股票的状态
dp[i][1]：保持卖出股票的状态
dp[i][2]：卖出股票状态
dp[i][3]：冷冻期

为什么要把 不持有股票状态拆分为两个部分【保持卖出股票的状态、卖出股票状态】，因为有冷冻期。必须前一天是卖出股票的状态，那么下一天才能是冷冻期

2、递推公式
持有股票状态：
1、i-1天就持有：dp[i][0] = dp[i-1][0];
2、冷冻期之后买入股票：dp[i][0] = dp[i-1][3] - prices[i];
3、冷冻期之后一直没有操作，一直都是保持卖出股票状态，直到第i天买入：dp[i][0] = dp[i-1][1] - prices[i];
因此：dp[i][0] = Math.max(dp[i-1][0], dp[i-1][3] - prices[i], dp[i][0] = dp[i-1][1] - prices[i])

保持卖出股票状态：
1、前一天就是保持卖出股票的状态：dp[i][1] = dp[i-1][1];
2、前一天是冷冻期，dp[i][1] = dp[i-1][3]
因此：dp[i][1] = Math.max(dp[i-1][1] , dp[i-1][3])

卖出股票状态：
1、前i-1天持有股票状态，第i天卖出股票.dp[i][2] = dp[i-1][0]+prices[i];
因此：dp[i][2]=dp[i-1][0]+prices[i];

冷冻期状态
1、前一天卖出股票状态，第i天就是冷冻期 dp[i][3] = dp[i-1][2]
因此：dp[i][3] = dp[i-1][2];

3、初始化
dp[0][0] = -prices[0];
dp[0][1] 在dp[i][0] = Math.max(dp[i-1][0], dp[i-1][3] - prices[i], dp[i][0] = dp[i-1][1] - prices[i]) 这个状态下会用到，假设i=1带入之后：
dp[1][0] = max(dp[0][0],dp[0][3]-prices[1], dp[0][1]-prices[1]);
dp[0][1] = 0;

dp[0][2] = 0;
dp[0][3] = 0;

4、遍历顺序
从前向后遍历，因为dp[i]，依靠dp[i - 1]的数值。

class Solution {public int maxProfit(int[] prices) {int[][] dp = new int[prices.length][4];//初始化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(Math.max(dp[i-1][0],dp[i-1][1]-prices[i]),dp[i-1][3]-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(Math.max(dp[prices.length-1][3],dp[prices.length-1][2]),dp[prices.length-1][1]);}
}

四、买卖股票的最佳时机含手续费（力扣714）

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

在之前有用贪心算法进行求解：
贪心算法求解

分析：
买卖股票的最佳时机II 可以进行多次买卖，但多了手续费

dp[i][0]：表示第i天持有股票所得现金。
dp[i][1]：表示第i天不持有股票所得最多现金
dp[i][0] = max(dp[i-1][0],dp[i-1][1]-prices[i]-fee)
dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i]);

class Solution {public int maxProfit(int[] prices, int fee) {int[][] dp = new int[prices.length][2];dp[0][0] = -prices[0]-fee;for(int i=1;i<prices.length;i++){dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]-prices[i]-fee);dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);}return dp[prices.length-1][1];}
}

优化后（一维滚动数组）

class Solution {public int maxProfit(int[] prices, int fee) {int[] dp = new int[2];dp[0] = -prices[0]-fee;for(int i=1;i<prices.length;i++){dp[0] = Math.max(dp[0],dp[1]-prices[i]-fee);dp[1] = Math.max(dp[1],dp[0]+prices[i]);}return dp[1];}
}

---

股票买卖问题总结

买卖股票的最佳时机（力扣121） 只能买卖一次
dp[i][0]:持有股票的状态
dp[i][1]:不持有股票的状态
dp[0][0] = -prices[0];
dp[0][1] = 0;
dp[i][0] = max(dp[i-1][0], -prices[i])
dp[i][1] = max(dp[i-1][1] , dp[i-1][0]+prices[i])

买卖股票的最佳时机||（力扣122）可以买卖多次
dp[i][0]:持有股票的状态
dp[i][1]:不持有股票的状态
dp[0][0] = -prices[0];
dp[0][1] = 0;
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])
细微变化在于持有股票状态的递推过程

买卖股票的最佳时机|||（力扣123）最多买卖2次
dp[i][0] 不操作
dp[i][1]:第一次持有股票状态
dp[i][2]:第一次不持有股票状态
dp[i][3]:第二次持有股票状态
dp[i][4]:第二次不持有股票状态
初始化
dp[0][0]= 0
dp[0][1] = -prices[0];
dp[0][2] = 0;
dp[0][3] = -prices[0];
dp[i][0] = dp[i-1][0]
dp[i][1] = max(dp[i-1][1],-prices[i])
dp[i][2] = max(dp[i-1][2], dp[i-1][1]+prices[i])
dp[i][3] = max(dp[i-1][3], dp[i-1][2]-prices[i])
dp[i][4] = max(dp[i-1][4], dp[i-1][3]+prices[i])

买卖股票的最佳时机IV（力扣188） 最多买卖k次
dp[i][0] 不操作
dp[i][1]:第一次持有股票状态
dp[i][2]:第一次不持有股票状态
dp[i][3]:第二次持有股票状态
dp[i][4]:第二次不持有股票状态
……
0 ----- 2*k
奇数是持有股票状态
偶数是卖出股票状态
初始化时：
if(j%2==1) dp[0][j] = -prices[0];
奇数时：dp[i][j] = max(dp[i-1][j],dp[i-1][j-1] - prices[i])
偶数时：dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j] +prices[i])

最佳买卖股票时机含冷冻期（力扣309） 买卖多次，卖出后有一天是冷冻期
dp[i][0]:持有股票的状态
dp[i][1]:保持卖出股票的状态
dp[i][2]:卖出股票的状态
dp[i][3]:冷冻期
初始化
dp[0][0] = -prices[0];
dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i], 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]

买卖股票的最佳时机含手续费（力扣714）买卖多次，每次都有手续费
dp[i][0]:持有股票的状态
dp[i][1]:不持有股票的状态
dp[0][0] = -prices[0]-fee;
dp[0][1] = 0;
dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i]-fee)
dp[i][1] = max(dp[i-1][1] , dp[i-1][0]+prices[i])
细微变化在于多减去手续费