188. Best Time to Buy and Sell Stock IV

dp

time: O(nk)

space: O(nk)

注意 n/2 這件事

class Solution {
    public int maxProfit(int k, int[] prices) {
        /*
            dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
            dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
        */
        
        if (prices == null || prices.length == 0 || prices.length < 2 || k == 0) return 0;
        
        int n = prices.length;
        
        if (k >= n/2) return maxProfit(prices);

        int dp[][][] = new int[n][k+1][2];

        for (int i = 0; i <= k; i++) {
            dp[0][i][0] = 0;
            dp[0][i][1] = -prices[0];
        }
        
        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 maxProfit(int[] prices) {
        int res = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                res += prices[i] - prices[i - 1];
            }
        }
        return res;
    }

}

more simple

因為其實只用到 i 天和 i-1 的資料, 所以第一維可以去掉

time: O(nk)

space: O(nk)

class Solution {
    public int maxProfit(int k, int[] prices) {
        /*
            dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
            dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
        */
        
        if (prices == null || prices.length == 0 || prices.length < 2 || k == 0) return 0;
        
        int n = prices.length;
        
        if (k >= n/2) return maxProfit(prices);

        
        int dp[][] = new int[k+1][2];

        for (int i = 0; i <= k; i++) {
            dp[i][0] = 0;
            dp[i][1] = -prices[0];
        }
        
        int res = Integer.MIN_VALUE;
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= k; j++) {
                dp[j][0] = Math.max(dp[j][0], dp[j][1] + prices[i]);
                dp[j][1] = Math.max(dp[j][1], dp[j-1][0] - prices[i]);
            }
        }
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                res = Math.max(res, dp[j][0]);
            }
        }
        return dp[k][0];
    }
    
    private int maxProfit(int[] prices) {
        int res = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                res += prices[i] - prices[i - 1];
            }
        }
        return res;
    }

}