Share my DP solution (By State Machine Thinking)


  • 542
    N

    Hi,

    I just come across this problem, and it's very frustating since I'm bad at DP.

    So I just draw all the actions that can be done.

    Here is the drawing (Feel like an elementary ...)

    enter image description here

    There are three states, according to the action that you can take.

    Hence, from there, you can now the profit at a state at time i as:

    s0[i] = max(s0[i - 1], s2[i - 1]); // Stay at s0, or rest from s2
    s1[i] = max(s1[i - 1], s0[i - 1] - prices[i]); // Stay at s1, or buy from s0
    s2[i] = s1[i - 1] + prices[i]; // Only one way from s1
    

    Then, you just find the maximum of s0[n] and s2[n], since they will be the maximum profit we need (No one can buy stock and left with more profit that sell right :) )

    Define base case:

    s0[0] = 0; // At the start, you don't have any stock if you just rest
    s1[0] = -prices[0]; // After buy, you should have -prices[0] profit. Be positive!
    s2[0] = INT_MIN; // Lower base case
    

    Here is the code :D

    class Solution {
    public:
    	int maxProfit(vector<int>& prices){
    		if (prices.size() <= 1) return 0;
    		vector<int> s0(prices.size(), 0);
    		vector<int> s1(prices.size(), 0);
    		vector<int> s2(prices.size(), 0);
    		s1[0] = -prices[0];
    		s0[0] = 0;
    		s2[0] = INT_MIN;
    		for (int i = 1; i < prices.size(); i++) {
    			s0[i] = max(s0[i - 1], s2[i - 1]);
    			s1[i] = max(s1[i - 1], s0[i - 1] - prices[i]);
    			s2[i] = s1[i - 1] + prices[i];
    		}
    		return max(s0[prices.size() - 1], s2[prices.size() - 1]);
    	}
    };

  • 0
    D
    This post is deleted!

  • 3
    D

    Much simpler to understand than those DP solutions.


  • 21
    H

    This is one of the best explanations for this kind of problems! As the state transitions only involve limited states and steps, we should be able to improve the space complexity to O(1):

    int maxProfit(vector<int>& prices) {
        int sold = 0, hold = INT_MIN, rest = 0;
        for (int i=0; i<prices.size(); ++i)
        {
            int prvSold = sold;
            sold = hold + prices[i];
            hold = max(hold, rest-prices[i]);
            rest = max(rest, prvSold);
        }
        return max(sold, rest);
    }

  • 1
    N

    Yep, it's definitely right to solve the problem in O(1) space complexity. I'm just lazy though :)
    May I use your code, and add them below my solution?


  • 0

    Cool! Brilliant!


  • 21
    S

    This is one of the best explanations I have seen so far.


  • 0
    T

    I also think so, great state machine thinking


  • 0
    R

    Very intuitive and Clean approach,
    Thanks a lot for sharing this, specially drawing states :)


  • 0
    F
    This post is deleted!

  • 7
    F

    FSM explanation of DP made my day. A good example of: One graph = 1000 words.
    Here is the java version with rolling array for O(1) space.

    public int maxProfitFSM(int[] prices) {
        if (prices == null || prices.length < 2)  return 0;
        int[] s0 = new int[2];
        int[] s1 = new int[2];
        int[] s2 = new int[2];
        s0[0] = 0;
        s1[0] = -prices[0];
        s2[0] = Integer.MIN_VALUE;
    
        for (int i = 1; i < prices.length; ++i) {
          s0[i%2] = Math.max(s0[(i-1)%2], s2[(i-1)%2]);
          s1[i%2] = Math.max(s1[(i-1)%2], s0[(i-1)%2] - prices[i]);
          s2[i%2] = s1[(i-1)%2] + prices[i];
        }
    
        return Math.max(s0[(prices.length-1)%2], s2[(prices.length-1)%2]);
    }

  • 0
    C

    Thanks for sharing! You use the state machine to simply the thinking process. Genius idea!


  • 0
    M

    great solution


  • 0
    K

    @halet.chen can you explain? i'm kind of lost.


  • 1

    This is a great method. However, Is this a general algorithm which we can use to solve a whole class of similar problems? For example, I heard DFA can be used to solve wildcard matching. Can you provide a reference where I can find more examples and learn this algorithm formally? Thank you so much!


  • 0
    N

    @xuyirui Sorry this is the first time I heard about DFA. I come up with this solution just the moment I solve this problem. I don't know about the general case, but I have solved other similar problems (Best time to buy & sell stocks) by this approach. I hope that someone with more knowledge than me can provide you a better answer :)


  • 1

    unbelievable! you must be genius. you invented a new method!


  • 0
    P

    Most Greatest explanation!


  • 16
    X

    This is much clear solution than the others. Can be easy extends to O(1) space using this idea.

       int maxProfit(vector<int>& prices) {
            if (prices.size() < 2) return 0;
            int s0 = 0, s1 = -prices[0], s2 = 0;
            for (int i = 1; i < prices.size(); ++i) {
                int last_s2 = s2;
                s2 = s1 + prices[i];
                s1 = max(s0 - prices[i], s1);
                s0 = max(s0, last_s2);
            }
            return max(s0, s2);
        }

  • 0
    Z

    Thanks for the enlightening article. in fact, you can plug s2[i] = s1[i - 1] + prices[i] into s0[i] = max(s0[i - 1], s2[i - 1]) to save the space for s2.


Log in to reply
 

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