LeetCode 188. Best Time to Buy and Sell Stock IV (Java版; Hard)

素颜马尾好姑娘i 2023-07-18 06:15 17阅读 0赞

### [welcome to my blog][] ###

## LeetCode 188. Best Time to Buy and Sell Stock IV (Java版; Hard) ##

#### 题目描述 ####

Say you have an array for which the i-th element is the price of a given stock on day i.
    
    Design an algorithm to find the maximum profit. You may complete at most k transactions.
    
    Note:
    You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
    
    Example 1:
    
    Input: [2,4,1], k = 2
    Output: 2
    Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
    Example 2:
    
    Input: [3,2,6,5,0,3], k = 2
    Output: 7
    Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
                 Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

#### 第一次做; 动态规划; 核心: 1) 最多进行n/2次交易, 所以k>=n/2时, k就没有意义了, 也就不用考虑k的状态了 2) 只能在买入时让交易次数减一, 不能在卖出时让交易次数减一, 会跟dp\[i\]\[0\]\[1\]=min冲突 ####

class Solution { 
        public int maxProfit(int k, int[] prices) { 
            if(prices==null || prices.length==0){ 
                return 0;
            }
            int n = prices.length;
            // n天, 最多有n/2次交易, 所以当k超过n/2时就意味着没有交易次数限制了, 不需要考虑k了
            if(k>=n/2){ 
                return maxProfit2(prices);
            }
            
            int[][][] dp = new int[n][k+1][2];
            for(int j=1; j<=k; j++){ 
                dp[0][j][1] = -prices[0];
            }
            for(int i=0; i<n; i++){ 
                //这是不可能出现的情况; 这里其实也隐藏了只能在买入时减少交易次数; 
                //在某一次卖出后k变成0, 此时还能再买入股票, 所以dp[i][0][1]这种状态是可能的
                dp[i][0][1] = Integer.MIN_VALUE;
            }
            //
            for(int i=1; i<n; i++){ 
                for(int j=1; j<=k; 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[n-1][k][0];
        }
    
        private int maxProfit2(int[] prices){ 
            int n = prices.length;
            int[][] dp = new int[n][2];
            dp[0][1] = -prices[0];
            for(int i=1; i<n; 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[n-1][0];
        }
    }

#### 第一次做; 动态规划; 超出内存限制209/211 ####

class Solution { 
        public int maxProfit(int k, int[] prices) { 
            if(prices==null || prices.length==0){ 
                return 0;
            }
            int n = prices.length;
            int[][][] dp = new int[n][k+1][2];
            for(int j=1; j<=k; j++){ 
                dp[0][j][1] = -prices[0];
            }
            for(int i=0; i<n; i++){ 
                //这是不可能出现的情况; 这里其实也隐藏了只能在买入时减少交易次数; 
                //在某一次卖出后k变成0, 此时还能再买入股票, 所以dp[i][0][1]这种状态是可能的
                dp[i][0][1] = Integer.MIN_VALUE;
            }
            //
            for(int i=1; i<n; i++){ 
                for(int j=1; j<=k; 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[n-1][k][0];
        }
    }

[welcome to my blog]: https://littlehaes.com