代码随想录算法训练营day42｜动态规划part09

第一题是：188. Best Time to Buy and Sell Stock IV

// 版本一: 三维 dp数组
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 + 1][2];// dp数组初始化// 初始化所有的交易次数是为确保 最后结果是最多 k 次买卖的最大利润for (int i = 0; i <= k; i++) {dp[0][i][1] = -prices[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]);}}return dp[len - 1][k][0];}
}// 版本二: 二维 dp数组
class Solution {public int maxProfit(int k, int[] prices) {if (prices.length == 0) return 0;// [天数][股票状态]// 股票状态: 奇数表示第 k 次交易持有/买入, 偶数表示第 k 次交易不持有/卖出, 0 表示没有操作int len = prices.length;int[][] dp = new int[len][k*2 + 1];// dp数组的初始化, 与版本一同理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];}
}//版本三：一维 dp数组 (下面有和卡哥邏輯一致的一維數組JAVA解法)
class Solution {public int maxProfit(int k, int[] prices) {if(prices.length == 0){return 0;}if(k == 0){return 0;}// 其实就是123题的扩展，123题只用记录2次交易的状态// 这里记录k次交易的状态就行了// 每次交易都有买入，卖出两个状态，所以要乘 2int[] dp = new int[2 * k];// 按123题解题格式那样，做一个初始化for(int i = 0; i < dp.length / 2; i++){dp[i * 2] = -prices[0];}for(int i = 1; i <= prices.length; i++){dp[0] = Math.max(dp[0], -prices[i - 1]);dp[1] = Math.max(dp[1], dp[0] + prices[i - 1]);// 还是与123题一样，与123题对照来看// 就很容易啦for(int j = 2; j < dp.length; j += 2){dp[j] = Math.max(dp[j], dp[j - 1] - prices[i-1]);dp[j + 1] = Math.max(dp[j + 1], dp[j] + prices[i - 1]);}}// 返回最后一次交易卖出状态的结果就行了return dp[dp.length - 1];}
}

class Solution {public int maxProfit(int k, int[] prices) {//edge casesif(prices.length == 0 || k == 0)return 0;int dp[] = new int [k * 2 + 1];//和卡哥邏輯一致，奇數天購入股票，故初始化只初始化奇數天。for(int i = 1; i < 2 * k + 1; i += 2){dp[i] = -prices[0];}for(int i = 1; i < prices.length; i++){ //i 從 1 開始，因爲第 i = 0 天已經透過初始化完成了。for(int j = 1; j < 2 * k + 1; j++){ //j 從 1 開始，因爲第 j = 0 天已經透過初始化完成了。//奇數天購買if(j % 2 == 1)dp[j] = Math.max(dp[j], dp[j - 1] - prices[i]);//偶數天賣出elsedp[j] = Math.max(dp[j], dp[j - 1] + prices[i]);}//打印DP數組//for(int x : dp)//    System.out.print(x +", ");//System.out.println();}//return 第2 * k次賣出的獲利。return dp[2 * k];}
}

第二题：309. Best Time to Buy and Sell Stock with Cooldown 

class Solution {public int maxProfit(int[] prices) {if (prices == null || prices.length < 2) {return 0;}int[][] dp = new int[prices.length][2];// bad casedp[0][0] = 0;dp[0][1] = -prices[0];dp[1][0] = Math.max(dp[0][0], dp[0][1] + prices[1]);dp[1][1] = Math.max(dp[0][1], -prices[1]);for (int i = 2; i < prices.length; i++) {// dp公式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 - 2][0] - prices[i]);}return dp[prices.length - 1][0];}
}

//using 2*4 array for space optimization
//這裡稍微說一下，我在LeetCode提交的時候，2*4 2-D array的performance基本上和下面的1-D array performance差不多
//都是time: 1ms, space: 40.X MB （其實 length*4 的 2-D array也僅僅是space:41.X MB，看起來不多）
//股票累的DP題目大致上都是這樣，就當作是一個延伸就好了。真的有人問如何優化，最起碼有東西可以講。
class Solution {/**1. [i][0] holding the stock2. [i][1] after cooldown but stil not buing the stock3. [i][2] selling the stock4. [i][3] cooldown*/public int maxProfit(int[] prices) {int len = prices.length;int dp[][] = new int [2][4];dp[0][0] = -prices[0];for(int i = 1; i < len; i++){dp[i % 2][0] = Math.max(Math.max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] - prices[i]), dp[(i - 1) % 2][3] - prices[i]);dp[i % 2][1] = Math.max(dp[(i - 1) % 2][1], dp[(i - 1) % 2][3]);dp[i % 2][2] = dp[(i - 1) % 2][0] + prices[i];dp[i % 2][3] = dp[(i - 1) % 2][2];}return Math.max(Math.max(dp[(len - 1) % 2][1], dp[(len - 1) % 2][2]), dp[(len - 1) % 2][3]);}
}

// 一维数组优化
class Solution {public int maxProfit(int[] prices) {int[] dp=new int[4];dp[0] = -prices[0];dp[1] = 0;for(int i = 1; i <= prices.length; i++){// 使用临时变量来保存dp[0], dp[2]// 因为马上dp[0]和dp[2]的数据都会变 int temp = dp[0];int temp1 = dp[2];dp[0] = Math.max(dp[0], Math.max(dp[3], dp[1]) - prices[i]);dp[1] = Math.max(dp[1], dp[3]);dp[2] = temp + prices[i];dp[3] = temp1;}return Math.max(dp[3],Math.max(dp[1],dp[2]));}
}

//另一种解题思路
class Solution {public int maxProfit(int[] prices) {int[][] dp = new int[prices.length + 1][2];dp[1][0] = -prices[0];for (int i = 2; i <= prices.length; i++) {/*dp[i][0] 第i天持有股票收益;dp[i][1] 第i天不持有股票收益;情况一：第i天是冷静期，不能以dp[i-1][1]购买股票,所以以dp[i - 2][1]买股票，没问题情况二：第i天不是冷静期，理论上应该以dp[i-1][1]购买股票，但是第i天不是冷静期说明，第i-1天没有卖出股票，则dp[i-1][1]=dp[i-2][1],所以可以用dp[i-2][1]买股票，没问题*/dp[i][0] = Math.max(dp[i - 1][0], dp[i - 2][1] - prices[i - 1]);dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i - 1]);}return dp[prices.length][1];}
}

第三题：714. Best Time to Buy and Sell Stock with Transaction Fee

/*** 卖出时支付手续费* @param prices* @param fee* @return*/
public int maxProfit(int[] prices, int fee) {int len = prices.length;// 0 : 持股（买入）// 1 : 不持股（售出）// dp 定义第i天持股/不持股 所得最多现金int[][] dp = new int[len][2];dp[0][0] = -prices[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][0] + prices[i] - fee, dp[i - 1][1]);}return Math.max(dp[len - 1][0], dp[len - 1][1]);
}/*** 买入时支付手续费* @param prices* @param fee* @return*/
public int maxProfit(int[] prices, int fee) {int len = prices.length;// 0 : 持股（买入）// 1 : 不持股（售出）// dp 定义第i天持股/不持股 所得最多现金int[][] dp = new int[len][2];// 考虑买入的时候就支付手续费dp[0][0] = -prices[0] - fee;for (int i = 1; i < len; 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][0] + prices[i], dp[i - 1][1]);}return Math.max(dp[len - 1][0], dp[len - 1][1]);
}// 一维数组优化
class Solution {public int maxProfit(int[] prices, int fee) {int[] dp = new int[2];dp[0] = -prices[0];dp[1] = 0;for (int i = 1; i <= prices.length; i++) {dp[0] = Math.max(dp[0], dp[1] - prices[i - 1]);dp[1] = Math.max(dp[1], dp[0] + prices[i - 1] - fee);}return dp[1];}
}
```Java
//使用 2*2 array
class Solution {public int maxProfit(int[] prices, int fee) {int dp[][] = new int[2][2];int len = prices.length;//[i][0] = holding the stock//[i][1] = not holding the stockdp[0][0] = -prices[0];for(int i = 1; i < len; i++){dp[i % 2][0] = Math.max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] - prices[i]);dp[i % 2][1] = Math.max(dp[(i - 1) % 2][1], dp[(i - 1) % 2][0] + prices[i] - fee);}return dp[(len - 1) % 2][1];}
}