LeetCode Day 動態規劃第 9 部分

188. 買賣股票的最佳時機 IV

給你一個整數數組prices，其中prices[i]是給定股票在第i天的價格，以及一個整數k。

找出你能獲得的最大利潤。您最多可以完成 k 筆交易：即您最多可以買入 k 次，最多可以賣出 k 次。

注意：您不得同時進行多項交易（即您必須先賣出股票才能再次購買）。

範例1：

輸入：k = 2，價格 = [2,4,1]
輸出：2
說明：第 1 天買入（價格 = 2），第 2 天賣出（價格 = 4），利潤 = 4-2 = 2。
範例2：

輸入：k = 2，價格 = [3,2,6,5,0,3]
輸出：7
解釋：第 2 天買入（價格 = 2）並在第 3 天賣出（價格 = 6），利潤 = 6-2 = 4。然後在第 5 天買入（價格 = 0）並在第 6 天賣出（價格 = 3） ，利潤=3-0=3。

限制：

1 1 0 原始頁

    public int maxProfit(int k, int[] prices) {
        /**[0][0] do nothing in day 0
           [0][1] own the stock for 1st time in day 0
           [0][2] not own the stock for 1st time in day 0
           [0][3] own the stock for 2nd time in day 0
           [0][4] not own the stock for 2nd time in day 0
           ....
           [0][k*2-1] own the stock for kth time in day 0
           [0][k*2] not own the stock for kth time in day 0

           [1][1] = max([0][1],[0][0]-prices[1])
           [1][2] = max([0][2],[0][1]+prices[1])
           [1][3] = max([0][3],[0][2]-prices[1])

           [i][j] if j is odd means we need to pay for the stock or keep the own status
                  if j is even means we can sell the stock or keep the non-stock status

        */    
        int[][] dp = new int[prices.length+1][k*2+1];
        for(int i=1; i<=k*2; i+=2){
            dp[0][i] = -prices[0];
        }

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

309. 買賣股票的最佳時機（有冷卻時間）

給你一個陣列價格，其中prices[i]是給定股票第i天的價格。

找出你能獲得的最大利潤。您可以根據需要完成任意多次交易（即多次買入一股股票並賣出一股股票），但有以下限制：

賣出股票後，您無法在第二天（即冷卻一天）購買股票。
注意：您不能同時進行多項交易（即您必須先賣出股票才能再次購買）。

範例1：

輸入：價格 = [1,2,3,0,2]
輸出：3
說明：交易 = [買進、賣出、放涼、買進、賣出]
範例2：

輸入：價格 = [1]
輸出：0

限制：

1 0

    public int maxProfit(int[] prices) {

        /**
        [0] own the stock
        [1] colldown 
        [2] not own the stock 

         */

         int[][] dp = new int[prices.length][3];

         dp[0][0] = -prices[0];

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

        // Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);

         return Math.max(dp[prices.length-1][2],dp[prices.length-1][1]);

    }

請注意，當冷卻期時，我們無法購買新股票。

在此回歸關係中，它顯示 dp[2] 是我們更新的最後一個，以便我們可以繼續覆蓋冷卻條件。

714. 買賣股票並收取交易費的最佳時機

您將獲得一個價格數組，其中prices[i]是給定股票第i天的價格，以及代表交易費用的整數費用。

找出你能獲得的最大利潤。您可以完成任意數量的交易，但您需要為每筆交易支付交易費用。

注意：

您不得同時進行多項交易（即，您必須先賣出股票才能再次購買）。
每次買賣股票只收取一次交易費。

範例1：

輸入：價格 = [1,3,2,8,4,9]，費用 = 2
輸出：8
說明：最大利潤可以透過以下方式實現：

• 以價格[0] = 1購買
• 以價格[3] = 8 出售
• 以價格[4] = 4購買
• 以價格[5] = 9 出售 總利潤為 ((8 - 1) - 2) + ((9 - 4) - 2) = 8。 範例2：

輸入：價格 = [1,3,7,5,10,3]，費用 = 3
輸出：6

限制：

1 1 0 原始頁

我們唯一應該考慮的是增加交易費，但費用不會改變我們之前的邏輯

    public int maxProfit(int[] prices, int fee) {
        int[] dp = new int[2];
        int temp = 0;

        dp[0] = -prices[0];

        for(int i=1; i<prices.length; i++){
            temp = dp[1];
            dp[1] = Math.max(dp[1], dp[0] + prices[i] -fee);
            dp[0] = Math.max(dp[0], temp-prices[i]);

        }

        return dp[1]; 
    }

以上是LeetCode Day 動態規劃第 9 部分的詳細內容。更多資訊請關注PHP中文網其他相關文章！