LeetCode Day Dynamische Programmierung Teil 9

188. Beste Zeit zum Kaufen und Verkaufen von Aktien IV

Sie erhalten ein ganzzahliges Array „Preise“, wobei „Preise[i]“ der Preis einer bestimmten Aktie am i-ten Tag und eine Ganzzahl „k“ ist.

Finden Sie den maximalen Gewinn, den Sie erzielen können. Sie können höchstens k Transaktionen abschließen: d. h. Sie dürfen höchstens k-mal kaufen und höchstens k-mal verkaufen.

Hinweis: Sie dürfen nicht mehrere Transaktionen gleichzeitig durchführen (d. h. Sie müssen die Aktie verkaufen, bevor Sie erneut kaufen).

Beispiel 1:

Eingabe: k = 2, Preise = [2,4,1]
Ausgabe: 2
Erläuterung: Kaufen Sie am Tag 1 (Preis = 2) und verkaufen Sie am Tag 2 (Preis = 4), Gewinn = 4-2 = 2.
Beispiel 2:

Eingabe: k = 2, Preise = [3,2,6,5,0,3]
Ausgabe: 7
Erläuterung: Kaufen Sie am 2. Tag (Preis = 2) und verkaufen Sie am 3. Tag (Preis = 6), Gewinn = 6-2 = 4. Dann kaufen Sie am 5. Tag (Preis = 0) und verkaufen Sie am 6. Tag (Preis = 3). , Gewinn = 3-0 = 3.

Einschränkungen:

1 <= k <= 100
1 <= Preise.Länge <= 1000
0 <= Preise[i] <= 1000
Originalseite

    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. Beste Zeit zum Kaufen und Verkaufen von Aktien mit Abklingzeit

Sie erhalten eine Reihe von Preisen, wobei „Preise[i]“ der Preis einer bestimmten Aktie am i-ten Tag ist.

Finden Sie den maximalen Gewinn, den Sie erzielen können. Sie können so viele Transaktionen durchführen, wie Sie möchten (d. h. eine Aktie kaufen und eine Aktie mehrmals verkaufen), mit den folgenden Einschränkungen:

Nachdem Sie Ihre Aktien verkauft haben, können Sie am nächsten Tag (d. h. Abklingzeit an einem Tag) keine Aktien mehr kaufen.
Hinweis: Sie dürfen nicht mehrere Transaktionen gleichzeitig durchführen (d. h. Sie müssen die Aktie verkaufen, bevor Sie erneut kaufen).

Beispiel 1:

Eingabe: Preise = [1,2,3,0,2]
Ausgabe: 3
Erläuterung: Transaktionen = [kaufen, verkaufen, Abklingzeit, kaufen, verkaufen]
Beispiel 2:

Eingabe: Preise = [1]
Ausgabe: 0

Einschränkungen:

1 <= Preise.Länge <= 5000
0 <= Preise[i] <= 1000

    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]);

    }

Achten Sie darauf, dass wir in der Abklingzeit keine neuen Aktien kaufen können.

In dieser Regressionsbeziehung zeigt es, dass dp[2] der letzte Wert ist, den wir aktualisieren, damit wir die Abklingbedingung weiterhin abdecken können.

714. Beste Zeit zum Kaufen und Verkaufen von Aktien mit Transaktionsgebühr

Sie erhalten ein Array von Preisen, wobei „prices[i]“ der Preis einer bestimmten Aktie am i-ten Tag und eine ganzzahlige Gebühr ist, die eine Transaktionsgebühr darstellt.

Finden Sie den maximalen Gewinn, den Sie erzielen können. Sie können so viele Transaktionen durchführen, wie Sie möchten, müssen jedoch für jede Transaktion die Transaktionsgebühr bezahlen.

Hinweis:

Sie dürfen nicht mehrere Transaktionen gleichzeitig durchführen (d. h. Sie müssen die Aktie verkaufen, bevor Sie erneut kaufen).
Die Transaktionsgebühr wird nur einmal pro Aktienkauf und -verkauf erhoben.

Beispiel 1:

Eingabe: Preise = [1,3,2,8,4,9], Gebühr = 2
Ausgabe: 8
Erläuterung: Der maximale Gewinn kann erzielt werden durch:

• Kauf zu Preisen[0] = 1
• Verkauf zu Preisen[3] = 8
• Kauf zu Preisen[4] = 4
• Verkauf zu Preisen[5] = 9 Der Gesamtgewinn beträgt ((8 - 1) - 2) + ((9 - 4) - 2) = 8. Beispiel 2:

Eingabe: Preise = [1,3,7,5,10,3], Gebühr = 3
Ausgabe: 6

Einschränkungen:

1 <= Preise.Länge <= 5 * 10^4
1 <= Preise[i] < 5 * 10^4
0 <= Gebühr < 5 * 10^4
Originalseite

Das Einzige, was wir in Betracht ziehen sollten, ist, die Transaktionsgebühr hinzuzufügen, aber die Gebühr wird unsere bisherige Logik nicht ändern

    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]; 
    }

Das obige ist der detaillierte Inhalt vonLeetCode Day Dynamische Programmierung Teil 9. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!