注意：123和124是一個(gè)思路，他們和后面的兩題思路不一樣。123 124的思路主線是k次，所以對某天的股票，第k次買入 = 第k-1次賣出+p(這里的max操作先省略)，第k次賣出=第k次買入后+p；

后兩題主要是天數(shù)的關(guān)系，k與k-1天關(guān)聯(lián)。

//121. 買賣股票的最佳時(shí)機(jī)public int maxProfit(int[] prices){if(prices.length==0) return 0;int res = 0;int min = prices[0];for (int p : prices) {min = Math.min(min,p);res = Math.max(res,p-min);}return res;}//122. 買賣股票的最佳時(shí)機(jī) IIpublic int maxProfit2(int[] prices) {int res = 0;if(prices.length<2)return 0;for(int i = 1;i<prices.length;i++){res += prices[i-1]<prices[i]?prices[i]-prices[i-1]:0;}return res;}//123. 買賣股票的最佳時(shí)機(jī) IIIpublic int maxProfit3(int[] prices) {int fbuy = -999999,fsel = 0;int sbuy = -999999,ssel = 0;for(int p:prices){fbuy = Math.max(fbuy,-p);fsel = Math.max(fsel,fbuy + p);sbuy = Math.max(sbuy,fsel-p);ssel = Math.max(ssel,sbuy+p);}return ssel;}//188. 買賣股票的最佳時(shí)機(jī) IVpublic int maxProfit(int k, int[] prices) {if (k<1 || prices.length<2)return 0;if (k>prices.length/2) return maxProfit2(prices);//k足夠大int[][] dp = new int[k][2];//第i天最后一個(gè)操作是 0買入 1賣出 時(shí)的最大收益；for (int i = 0; i < k; i++) dp[i][0] = Integer.MIN_VALUE;for (int p : prices){dp[0][0] = Math.max(dp[0][0],-p);dp[0][1] = Math.max(dp[0][1],dp[0][0]+p);for (int i = 1;i<k;i++){dp[i][0] = Math.max(dp[i][0],dp[i-1][1]-p);dp[i][1] = Math.max(dp[i][1],dp[i][0] + p);}}return dp[k-1][1];} //309. 最佳買賣股票時(shí)機(jī)含冷凍期public int maxProfit_(int[] prices) {//買賣股票系列問題if(prices == null || prices.length < 2){return 0;}int n = prices.length;int [][] dp = new int[n][3];//買入 冷凍 賣出，第i天最后一個(gè)操作是xx時(shí)的最大收益；dp[0][0] = -prices[0];dp[0][1] = 0;dp[0][2] = 0;for(int i = 1;i<n;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][2]);//最后是冷凍 包含昨天就冷凍和昨天賣出今天冷凍dp[i][2] = dp[i-1][0]+prices[i];//最后是賣出 (不包含昨天就賣出) 昨天買入 今天賣出}return Math.max(dp[n-1][1],dp[n-1][2]);} //714. 買賣股票的最佳時(shí)機(jī)含手續(xù)費(fèi)//dp 設(shè)置兩個(gè)數(shù)組通用解法 二維數(shù)組也可public int maxProfit(int[] prices, int fee) {int n = prices.length;if(n<2)return 0;/*int[] dp1 = new int[n];//have stock in i_dayint[] dp2 = new int[n];//dont havadp1[0] = -prices[0];dp2[0] = 0;for(int i = 1;i<n;i++){dp1[i] = Math.max(dp1[i-1],dp2[i-1]-prices[i]);dp2[i] = Math.max(dp2[i-1],dp1[i-1]+prices[i]-fee);}return dp2[n-1];*/int[][] dp = new int[n][2];//0 最后操作是買入 1 最后操作是賣出dp[0][0] = -prices[0];dp[0][1] = 0;for (int i = 1; i < n; 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[n-1][1];}

?

總結(jié)

以上是生活随笔為你收集整理的动态规划之力扣股票类问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。