LeetCode Day 動的プログラミング パート 9

188. 株式の売買に最適な時期 IV

整数の配列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 株を複数回売却)。

株式を売却した後、翌日 (つまり、1 日のクールダウン) には株式を購入することはできません。
注: 複数の取引を同時に行うことはできません (つまり、株式を再度購入する前に売却する必要があります)。

例 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:

入力: 価格 = [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 中国語 Web サイトの他の関連記事を参照してください。