Pengaturcaraan Dinamik Hari LeetCode Bahagian 9

188. Masa Terbaik untuk Membeli dan Menjual Saham IV

Anda diberi harga tatasusunan integer dengan harga[i] ialah harga saham tertentu pada hari ke-i dan integer k.

Cari keuntungan maksimum yang anda boleh capai. Anda boleh menyelesaikan paling banyak k urus niaga: iaitu anda boleh membeli paling banyak k kali dan menjual paling banyak k kali.

Nota: Anda tidak boleh terlibat dalam berbilang transaksi serentak (iaitu, anda mesti menjual saham sebelum anda membeli semula).

Contoh 1:

Input: k = 2, harga = [2,4,1]
Keluaran: 2
Penjelasan: Beli pada hari 1 (harga = 2) dan jual pada hari 2 (harga = 4), untung = 4-2 = 2.
Contoh 2:

Input: k = 2, harga = [3,2,6,5,0,3]
Keluaran: 7
Penjelasan: Beli pada hari ke-2 (harga = 2) dan jual pada hari ke-3 (harga = 6), untung = 6-2 = 4. Kemudian beli pada hari ke-5 (harga = 0) dan jual pada hari ke-6 (harga = 3) , untung = 3-0 = 3.

Kekangan:

1 <= k <= 100
1 <= harga.panjang <= 1000
0 <= harga[i] <= 1000
Halaman Asal

    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. Masa Terbaik untuk Membeli dan Menjual Saham dengan Cooldown

Anda diberi harga tatasusunan di mana harga[i] ialah harga saham tertentu pada hari ke-1.

Cari keuntungan maksimum yang anda boleh capai. Anda boleh melengkapkan seberapa banyak urus niaga yang anda suka (iaitu, beli satu dan jual satu bahagian saham berbilang kali) dengan sekatan berikut:

Selepas anda menjual saham anda, anda tidak boleh membeli saham pada hari berikutnya (iaitu, bertenang satu hari).
Nota: Anda tidak boleh terlibat dalam berbilang transaksi serentak (iaitu, anda mesti menjual saham sebelum anda membeli semula).

Contoh 1:

Input: harga = [1,2,3,0,2]
Keluaran: 3
Penjelasan: urus niaga = [beli, jual, cooldown, beli, jual]
Contoh 2:

Input: harga = [1]
Output: 0

Kekangan:

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

    }

Berhati-hati, bahawa apabila ia cooldown, kita tidak boleh membeli stok baru.

dalam hubungan regresi ini, ia menunjukkan dp[2] ialah yang terakhir yang kami kemas kini supaya kami boleh terus meliputi keadaan cooldown.

714. Masa Terbaik untuk Membeli dan Menjual Stok dengan Yuran Transaksi

Anda diberikan harga tatasusunan dengan harga[i] ialah harga saham tertentu pada hari ke-i dan yuran integer mewakili yuran transaksi.

Cari keuntungan maksimum yang anda boleh capai. Anda boleh menyelesaikan seberapa banyak transaksi yang anda suka, tetapi anda perlu membayar yuran transaksi untuk setiap transaksi.

Nota:

Anda tidak boleh terlibat dalam berbilang transaksi serentak (iaitu, anda mesti menjual saham sebelum anda membeli semula).
Yuran transaksi hanya dikenakan sekali untuk setiap pembelian dan penjualan stok.

Contoh 1:

Input: harga = [1,3,2,8,4,9], yuran = 2
Keluaran: 8
Penjelasan: Keuntungan maksimum boleh dicapai dengan:

• Membeli pada harga[0] = 1
• Jualan pada harga[3] = 8
• Membeli pada harga[4] = 4
• Jualan pada harga[5] = 9 Jumlah keuntungan ialah ((8 - 1) - 2) + ((9 - 4) - 2) = 8. Contoh 2:

Input: harga = [1,3,7,5,10,3], yuran = 3
Keluaran: 6

Kekangan:

1 <= harga.panjang <= 5 * 10^4
1 <= harga[i] < 5 * 10^4
0 <= yuran < 5 * 10^4
Halaman Asal

satu-satunya perkara yang perlu kami pertimbangkan ialah menambah yuran transaksi, tetapi yuran itu tidak akan mengubah logik kami sebelum ini

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

Atas ialah kandungan terperinci Pengaturcaraan Dinamik Hari LeetCode Bahagian 9. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!