Share my DP solution with different state definition


  • 1
    W
    public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        int len = prices.length;
        int[][] dp = new int[len][3];
        dp[0][0] = -prices[0]; dp[0][1] = 0; dp[0][2] = 0;
        int localMax = dp[0][0];
        for (int i = 1; i < len; i++) {
            dp[i][1] = localMax + prices[i]; //sell
            dp[i][0] = dp[i - 1][2] - prices[i]; // buy
            localMax = Math.max(localMax, dp[i][0]);
            dp[i][2] = Math.max(dp[i - 1][1], dp[i - 1][2]); //cooldown
        }
        int ans = Math.max(dp[len - 1][1], dp[len - 1][2]);
        ans = Math.max(ans, 0);
        return ans;
    }
    

    }

    what I am doing is the set

    dp[i][0] : maximum profits when ending with a *buy*   **at position i**;
    dp[i][1] : maximum profits when ending with a *sell*   **at position i**
    dp[i][2] : maximum profits when ending with a *rest*   **at position i**
    

    This way, we can generate following

     dp[i][1] = localMax + prices[i];     // last maxbuy + prices at i
     dp[i][0] = dp[i - 1][2]
     dp[i][2] = Math.max(dp[i - 1][1], dp[i - 1][2]);  // little simplification here, dp[i - 1][0] for sure will not be the maximum, cause dp[i - 2][2] will be greater than that;

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.