188.買賣股票的最佳時機IV
題目鏈接:188.買賣股票的最佳時機IV
文檔講解:代碼隨想錄
狀態:不會
思路:
在股票買賣1使用一維dp的基礎上,升級成二維的即可。
- 定義dp[k+1][2],其中 dp[j][0] 表示第j次交易后持有股票的最大利潤,dp[j][1] 表示第j次交易后不持有股票的最大利潤。
- 初始化時,對所有持有股票的情況要變成dp[i][0] = -prices[0];
題解:
要注意: dp[j][0] = Math.max(dp[j][0], dp[j - 1][1] - prices[i]);
dp[j - 1][1] - prices[i] 是因為買入股票的操作要用dp[j-1][1],也就是上次賣出去得到的錢來買這次的股票
public int maxProfit(int k, int[] prices) {// 特殊情況處理,如果價格數組為空或只有一個元素,返回0if (prices.length == 0) return 0;// dp數組定義為k+1行,2列// dp[j][0] 表示第j次交易后持有股票的最大利潤// dp[j][1] 表示第j次交易后不持有股票的最大利潤int[][] dp = new int[k + 1][2];// 初始化第1到第k次交易后的持有股票的最大利潤為 -prices[0]for (int i = 1; i <= k; i++) {dp[i][0] = -prices[0];}// 遍歷每一天的股票價格for (int i = 1; i < prices.length; i++) {// 倒序遍歷每一次交易,也可以正序,但是倒序更快一點for (int j = k; j >= 1; j--) {// 更新第j次交易后不持有股票的最大利潤dp[j][1] = Math.max(dp[j][1], dp[j][0] + prices[i]);// 更新第j次交易后持有股票的最大利潤// dp[j - 1][1] - prices[i] 是因為買入股票的操作要用dp[j-1][1],也就是上次賣出去得到的錢來買這次的股票dp[j][0] = Math.max(dp[j][0], dp[j - 1][1] - prices[i]);}}// 返回最多k次交易后不持有股票的最大利潤return dp[k][1];}
309.最佳買賣股票時機含冷凍期
題目鏈接:309.最佳買賣股票時機含冷凍期
文檔講解:代碼隨想錄
狀態:不會
思路:
第i天的最大收益由持有和不持有股票兩種狀態推導出來,考慮到由冷凍期,那么第i天持有股票可以考慮跳過昨天,從前天推導。
假設有今天持股情況下的最大收益 dp[i][0]、昨天不持股的最大收益 dp[i?1][0]、昨天持股的最大收益 dp[i?1][0]、前天不持股的最大收益 dp[i?2][1],前天持股的最大收益 dp[i?2][0]。先將目光集中在前天,分別考慮前天持股與不持股的情況,試試能不能推導出今天的最大收益。
對于 dp[i?2][0] 來說,它表示前天結束時手中還有股票,那么如果昨天選擇將前天的股票賣掉,由于冷凍期的存在,今天是不能交易的,自然今天手中也不可能還有股票,推導不出 dp[i][0],因此這種情況可以直接忽略;如果前天選擇保留股票到昨天,昨天也只能繼續保留股票才能讓今天手中也有股票,這時 dp[i][0]=dp[i?1][0],這種情況已經在上面的狀態轉移方程中考慮到了,因此也不用擔心。
對于 dp[i?2][1] 來說,它表示前天結束時手中沒有股票,如果昨天買入股票,只能是將股票保留到今天才能推出 dp[i][0],這時 dp[i]=dp[i?1][0] 在狀態轉移方程中已經考慮到了;如果昨天不買入股票,那么由于昨天手中沒有股票,只能是今天買入,同時因為昨天沒交易,昨天的最大收益和前天相同 dp[i?1][1]=dp[i?2][1],所以這種情況的最大收益是 dp[i?2][1]?prices[i]。
題解:
public int maxProfit(int[] prices) {int n = prices.length;// 如果價格數組長度為0,直接返回0if (n == 0) {return 0;}// 定義一個二維數組 dp,dp[i][0] 表示第 i 天持有股票的最大利潤,// dp[i][1] 表示第 i 天不持有股票的最大利潤int[][] dp = new int[n + 1][2];// 初始化第一天的狀態dp[1][0] = -prices[0]; // 第一天持有股票,利潤為負的當前股票價格// 從第二天開始遍歷價格數組for (int i = 2; i <= n; i++) {// 第 i 天持有股票的最大利潤,可以選擇前一天也持有股票,或者前兩天不持有股票,今天買入dp[i][0] = Math.max(dp[i - 1][0], dp[i - 2][1] - prices[i - 1]);// 第 i 天不持有股票的最大利潤,可以選擇前一天也不持有股票,或者前一天持有股票,今天賣出dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i - 1]);}// 返回倒數第二天不持有股票的最大利潤return dp[n][1]; // 因為是倒數第二天,所以這里改為 dp[n][1]}
714.買賣股票的最佳時機含手續費
題目鏈接:714.買賣股票的最佳時機含手續費
文檔講解:代碼隨想錄
狀態:終于做出來一道了。。。。
思路:和股票買賣第2道題一樣,不過每次賣出的時候扣除手續費就好了。
題解:
public int maxProfit(int[] prices, int fee) {if (prices.length == 1) {return 0;}int hasStock = -prices[0]; // 第一天買入股票后的收益int noStock = 0; // 第一天不買股票的收益for (int i = 1; i < prices.length; i++) {// 今天選擇買入股票或者保持昨天持有股票的狀態hasStock = Math.max(hasStock, noStock - prices[i]);// 今天選擇賣出股票或者保持昨天沒有股票的狀態noStock = Math.max(noStock, hasStock + prices[i] - fee);}return noStock; // 最后一天不持有股票的最大收益
}