123. Best Time to Buy and Sell Stock III

1. what part I stuck?
I think i can directly solve the k way transactions, but I found it's not easy as I think.

2. After seeing solution, think about how this person came out this solution? what’s their thought process, why we have the same question and same knowledge, but I cant?
oh...just claim k 0~2 solutions...

3. note strategy! remember it!
list all dp k 0~2 solutions..., then use variables to improve space complexity.

DP

time: O(n)

space:O(n)

class Solution {
    public int maxProfit(int[] prices) {
        // at most 2 transaction
        int n = prices.length;
        
        int dp[][][] = new int[n][3][2];
        
        // 0 part can ignore, dont write!
//         dp[0][0][0] = 0;
//         dp[0][0][1] = 0;
        
//         dp[0][1][0] = 0;
        dp[0][1][1] = -prices[0];
        
        // dp[0][2][0] = 0; 
        dp[0][2][1] = -prices[0];

        // buy: k-1
        for (int i = 1; i < prices.length; i++) {
            dp[i][1][0] = Math.max(dp[i-1][1][0], dp[i-1][1][1] + prices[i]);
            dp[i][1][1] = Math.max(dp[i-1][1][1], dp[i-1][0][0] - prices[i]);
            dp[i][2][0] = Math.max(dp[i-1][2][0], dp[i-1][2][1] + prices[i]);
            dp[i][2][1] = Math.max(dp[i-1][2][1], dp[i-1][1][0] - prices[i]);
        }
        return Math.max(dp[n-1][1][0], dp[n-1][2][0]);
    }
}

use variables

time: O(n)

space: O(1)

class Solution {
    public int maxProfit(int[] prices) {
        // at most 2 transaction
        int n = prices.length;
                
        int dp10 = 0;
        int dp11 = -prices[0];
        
        int dp20 = 0; 
        int dp21 = -prices[0];

        // buy: k-1
        for (int i = 1; i < n; i++) {
            int newDp10 = Math.max(dp10, dp11 + prices[i]);
            int newDp11 = Math.max(dp11, - prices[i]);
            int newDp20 = Math.max(dp20, dp21 + prices[i]);
            int newDp21 = Math.max(dp21, dp10 - prices[i]);
            dp10 = newDp10;
            dp11 = newDp11;
            dp20 = newDp20;
            dp21 = newDp21;
        }
        return Math.max(dp10, dp20);
    }
}