LeetCode188. The best time to buy and sell stocks IV

This paper is finally updated at 484 Days ago, , The information may have developed or changed .

One 、 Ideas

There is an upper limit to choice ,10 A lottery ticket for you to buy , The best you can buy is 10 Zhang . Why care about the number of choices ？ Because I have chosen the unlimited number of tradable times in the title ： Select the number of transactions , Choose the number of two trades . Then choose the best choice . The essence of dynamic programming is to find out the options , Then make a choice

Two 、 problem

Given an array of integers  prices , It's the first i Elements  prices[i] Is a given stock in the i Sky price .

Design an algorithm to calculate the maximum profit you can get . You can do at most k transaction .

Be careful ： You can't participate in multiple transactions at the same time （ You have to sell the stock before you buy it again ）.

Example 1：

 Input ：k = 2, prices = [2,4,1]
 Output ：2
 explain ： In the  1  God  ( Stock price  = 2)  Buy when , In the  2  God  ( Stock price  = 4)  Sell when , The exchange will make a profit  = 4-2 = 2 .

Copy

Example 2：

 Input ：k = 2, prices = [3,2,6,5,0,3]
 Output ：7
 explain ： In the  2  God  ( Stock price  = 2)  Buy when , In the  3  God  ( Stock price  = 6)  Sell when ,  The exchange will make a profit  = 6-2 = 4 .
      And then , In the  5  God  ( Stock price  = 0)  Buy when , In the  6  God  ( Stock price  = 3)  Sell when ,  The exchange will make a profit  = 3-0 = 3 .

Copy

Tips ：

• 0 <= k <= 100
• 0 <= prices.length <= 1000
• 0 <= prices[i] <= 1000

Related Topics

• Dynamic programming

\n

• 449
• 0

3、 ... and 、 Code

public int maxProfit(int k, int[] prices) {
            if (prices == null || prices.length == 0) {
                return 0;
            }
            int length = prices.length;
            if (k >= length / 2) {
                return maxProfit(prices);
            }
            int[][][] dp = new int[length][k + 1][2];
            for (int i = 1; i <= k; i++) {
                dp[0][i][0] = 0;
                dp[0][i][1] = -prices[0];
            }
            for (int i = 1; i < length; i++) {
                for (int j = k; j > 0; j--) {
                    dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
                    dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
                }
            }
            return dp[length - 1][k][0];
        }

        public int maxProfit(int[] prices) {
            if (prices == null || prices.length == 0) {
                return 0;
            }
            int length = prices.length;
            int[][] dp = new int[length][2];
            dp[0][0] = 0;
            dp[0][1] = -prices[0];
            for (int i = 1; i < length; i++) {
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            }
            return dp[length - 1][0];
        }

Copy

Post Views: 320