Programmation dynamique du LetCode Day, partie 9

188. Meilleur moment pour acheter et vendre des actions IV

Vous recevez un tableau de prix entiers où prix[i] est le prix d'une action donnée le ième jour et un entier k.

Trouvez le profit maximum que vous pouvez réaliser. Vous pouvez effectuer au plus k transactions : c'est-à-dire que vous pouvez acheter au plus k fois et vendre au plus k fois.

Remarque : vous ne pouvez pas effectuer plusieurs transactions simultanément (c'est-à-dire que vous devez vendre l'action avant d'acheter à nouveau).

Exemple 1 :

Entrée : k = 2, prix = [2,4,1]
Sortie : 2
Explication : Achetez le jour 1 (prix = 2) et vendez le jour 2 (prix = 4), profit = 4-2 = 2.
Exemple 2 :

Entrée : k = 2, prix = [3,2,6,5,0,3]
Sortie : 7
Explication : Achetez le jour 2 (prix = 2) et vendez le jour 3 (prix = 6), profit = 6-2 = 4. Puis achetez le jour 5 (prix = 0) et vendez le jour 6 (prix = 3) , profit = 3-0 = 3.

Contraintes :

1 <= k <= 100
1 <= prix.longueur <= 1000
0 <= prix[i] <= 1000
Page originale

    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. Meilleur moment pour acheter et vendre des actions avec un temps de recharge

Vous recevez un tableau de prix où prix[i] est le prix d'une action donnée le ième jour.

Trouvez le profit maximum que vous pouvez réaliser. Vous pouvez effectuer autant de transactions que vous le souhaitez (c'est-à-dire en acheter une et vendre une action plusieurs fois) avec les restrictions suivantes :

Après avoir vendu votre action, vous ne pouvez pas en acheter le lendemain (c'est-à-dire avec un délai de récupération d'un jour).
Remarque : Vous ne pouvez pas effectuer plusieurs transactions simultanément (c'est-à-dire que vous devez vendre l'action avant d'acheter à nouveau).

Exemple 1 :

Entrée : prix = [1,2,3,0,2]
Sortie : 3
Explication : transactions = [achat, vente, temps de recharge, achat, vente]
Exemple 2 :

Entrée : prix = [1]
Sortie : 0

Contraintes :

1 <= prix.longueur <= 5000
0 <= prix[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]);

    }

Faites attention, lorsque le temps de recharge est en cours, nous ne pouvons pas acheter un nouveau stock.

dans cette relation de régression, cela montre que dp[2] est le dernier que nous mettons à jour afin que nous puissions continuer à couvrir les conditions de refroidissement.

714. Meilleur moment pour acheter et vendre des actions avec frais de transaction

Vous recevez un tableau de prix où prix[i] est le prix d'une action donnée le ième jour, et un nombre entier représentant des frais de transaction.

Trouvez le profit maximum que vous pouvez réaliser. Vous pouvez effectuer autant de transactions que vous le souhaitez, mais vous devez payer les frais de transaction pour chaque transaction.

Remarque :

Vous ne pouvez pas effectuer plusieurs transactions simultanément (c'est-à-dire que vous devez vendre l'action avant d'acheter à nouveau).
Les frais de transaction ne sont facturés qu'une seule fois pour chaque achat et vente d'actions.

Exemple 1 :

Entrée : prix = [1,3,2,8,4,9], frais = 2
Sortie : 8
Explication : Le profit maximum peut être atteint par :

• Acheter à des prix[0] = 1
• Vendre à des prix[3] = 8
• Acheter à des prix[4] = 4
• Vendre à des prix[5] = 9 Le bénéfice total est ((8 - 1) - 2) + ((9 - 4) - 2) = 8. Exemple 2 :

Entrée : prix = [1,3,7,5,10,3], frais = 3
Sortie : 6

Contraintes :

1 <= prix.longueur <= 5 * 10^4
1 &Lt ;= prix[i] &Lt ; 5*10^4
0 <= frais < 5*10^4
Page originale

la seule chose que nous devrions considérer est d'ajouter les frais de transaction, mais les frais ne changeront pas notre logique précédente

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!