LeetCode Day動的プログラミングpart8

121. 株を売買するのに最適な時期

価格の配列が与えられます。ここで、prices[i] は i 日目の特定の株式の価格です。

ある株を買う日を選択し、その株を売るには将来の別の日を選択することで、利益を最大化したいと考えています。

この取引から達成できる最大の利益を返します。利益を達成できない場合は、0 を返します。

例 1:

入力: 価格 = [7,1,5,3,6,4]
出力: 5
説明: 2 日目に買い (価格 = 1)、5 日目に売る (価格 = 6)、利益 = 6-1 = 5。
販売する前に購入する必要があるため、2 日目に買って 1 日目に売ることはできないことに注意してください。
例 2:

入力: 価格 = [7,6,4,3,1]
出力: 0
説明: この場合、トランザクションは行われず、最大利益 = 0.

制約:

1 0 オリジナルページ

方法 1、貪欲なアルゴリズム

    public int maxProfit(int[] prices) {
        if(prices.length == 0){
            return 0;
        }

        int profit = 0;
        int buy = prices[0];
        for(int i=1; i<prices.length; i++ ){
            if(buy>=prices[i]){
                buy = prices[i];
            }else{
                profit = Math.max(profit, prices[i]-buy);
            }
        }
        return profit;
    }

時間 O(n) 空間 O(1)

方法 2 動的プログラミング

    public int maxProfit(int[] prices) {
        if(prices.length == 0){
            return 0;
        }

        // 2 means we have 2 different status (have owned stock or not )
        int[][] dp = new int[prices.length][2];

        // if we want to own the stock we should pay for the specific price
        dp[0][0] = -prices[0];
        for(int i=1; i<dp.length; i++){
            dp[i][0] = Math.max(dp[i-1][0], -prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], prices[i] + dp[i-1][0]);
        }
        // Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);
        return dp[dp.length-1][1];
    }

時間 O(n) 空間 O(n)
動的プログラミングは、特定の問題に対してのみ機能するわけではないため、貪欲なアルゴリズムよりも一般的です。

方法 2.1 (空間の複雑さを改善する)

    public int maxProfit(int[] prices) {
        if(prices.length == 0){
            return 0;
        }

        // 2 means we have 2 different status (have owned stock or not )
        int[] dp = new int[2];

        // if we want to own the stock we should pay for the specific price
        dp[0] = -prices[0];
        for(int i=1; i<prices.length; i++){
            dp[1] = Math.max(dp[1], prices[i] + dp[0]);
            dp[0] = Math.max(dp[0], -prices[i]);
        }
        // 
        return dp[1];
    }

ここでは、更新された dp[0] の代わりに以前の dp[0] を使用するため、最初に dp[1] を処理する必要があることに注意してください。

122. 株式の売買に最適な時期 II

整数配列の 価格 が与えられます。ここで、prices[i] は i 日目の特定の株式の価格です。

毎日、株式を購入または売却するか、あるいはその両方を決定で​​きます。いつでも保有できる株式は最大 1 株のみです。ただし、購入してその日にすぐに売ることは可能です。

達成可能な最大利益を見つけて返します。

例 1:

入力: 価格 = [7,1,5,3,6,4]
出力: 7
説明: 2 日目に買い (価格 = 1)、3 日目に売る (価格 = 5)、利益 = 5-1 = 4。
次に、4 日目に購入 (価格 = 3)、5 日目に売却 (価格 = 6)、利益 = 6-3 = 3 となります。
合計利益は 4 + 3 = 7 です。
例 2:

入力: 価格 = [1,2,3,4,5]
出力: 4
説明: 1 日目に買い (価格 = 1)、5 日目に売る (価格 = 5)、利益 = 5-1 = 4.
合計利益は 4.
例 3:

入力: 価格 = [7,6,4,3,1]
出力: 0
説明: プラスの利益を得る方法はないため、最大利益 0 を達成するために株を購入することはありません。

制約:

1 0

    public int maxProfit(int[] prices) {
        if(prices.length <1){
            return 0;
        }

        int[][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0];

        for(int i=1; i<prices.length; i++){
            //only when we do not own the stack we can buy a new stock
            dp[i][0] = Math.max(dp[i-1][1]-prices[i], dp[i-1][0]);
            dp[i][1] = Math.max(dp[i-1][0]+prices[i], dp[i-1][1]);
        }

        return dp[prices.length-1][1];
    }

ローリング配列メソッド

    public int maxProfit(int[] prices) {
        if(prices.length <1){
            return 0;
        }

        int[] dp = new int[2];
        dp[0] = -prices[0];

        for(int i=1; i<prices.length; i++){
            //only when we do not own the stack we can buy a new stock
            dp[1] = Math.max(dp[0]+prices[i], dp[1]);
            dp[0] = Math.max(dp[1]-prices[i], dp[0]);

        }

        return dp[1];
    }

123. 株式の売買に最適な時期 III

価格の配列が与えられます。ここで、prices[i] は i 日目の特定の株式の価格です。

達成できる最大の利益を見つけてください。最大 2 つのトランザクションを完了できます。

注: 複数の取引を同時に行うことはできません (つまり、株式を再度購入する前に売却する必要があります)。

例 1:

入力: 価格 = [3,3,5,0,0,3,1,4]
出力: 6
説明: 4 日目に買い (価格 = 0)、6 日目に売る (価格 = 3)、利益 = 3-0 = 3。
次に、7 日目に購入 (価格 = 1)、8 日目に売却 (価格 = 4)、利益 = 4-1 = 3 となります。
例 2:

入力: 価格 = [1,2,3,4,5]
出力: 4
説明: 1 日目に買い (価格 = 1)、5 日目に売る (価格 = 5)、利益 = 5-1 = 4.
同時に複数の取引を行っているため、1 日目に購入し、2 日目に購入して後で売却することはできないことに注意してください。再度購入する前に売却する必要があります。
例 3:

入力: 価格 = [7,6,4,3,1]
出力: 0
説明: この場合、トランザクションは行われません。つまり、最大利益 = 0.

制約:

1 0

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

        for(int i=1; i<prices.length; i++){

            dp[i][1] = Math.max(dp[i-1][0]-prices[i], dp[i-1][1]);
            dp[i][2] = Math.max(dp[i-1][1]+prices[i], dp[i-1][2]);
            dp[i][3] = Math.max(dp[i-1][2]-prices[i], dp[i-1][3]);
            dp[i][4] = Math.max(dp[i-1][3]+prices[i], dp[i-1][4]);
        }
        Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);

        return dp[prices.length-1][4];
    }

以上がLeetCode Day動的プログラミングpart8の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。