2 solutions, 2 states DP solutions, clear explanation!


  • 3

    Given any day I, its max profit status boils down to one of the two status below:

    (1) buy status:
    buy[I] represents the max profit at day I in buy status, given that you took buy action at day K, where K<=I. And you have the right to sell at day I+1, or do nothing.
    (2) sell status:
    sell[I] represents the max profit at day I in sell status, given that you took sell action at day K, where K<=I. And you have the right to buy at day I+1, or do nothing.

    Let's walk through from base case.

    Base case:
    We can start from buy status, which means we buy stock at day 0.
    buy[0]=-prices[0];
    Or we can start from sell status, which means we sell stock at day 0.
    Given that we don't have any stock at hand in day 0, we set sell status to be 0.
    sell[0]=0;

    Status transformation:
    At day I, we may buy stock or do nothing:
    buy[i] = Math.max(buy[i - 1], sell[i - 1] - prices[i]);
    Or
    At day I, we may sell stock or keep holding:
    sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);

    Finally:
    We will return sell[last_day] as our result, which represents the max profit at the last day, given that you took sell action at any day before the last day.

    We can apply transaction fee at either buy status or sell status.

    So here come our two solutions:

    Solution I -- pay the fee when buying the stock:

    public int maxProfit(int[] prices, int fee) {
            if (prices.length <= 1) return 0;
            int[] buy = new int[prices.length], sell = new int[prices.length];
            buy[0]=-prices[0]-fee;
            for (int i = 1; i<prices.length; i++) {
                buy[i] = Math.max(buy[i - 1], sell[i - 1] - prices[i] - fee); // keep the same as day i-1, or buy from sell status at day i-1
                sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]); // keep the same as day i-1, or sell from buy status at day i-1
            }
            return sell[prices.length - 1];
        }
    

    Solution II -- pay the fee when selling the stock:

        public int maxProfit(int[] prices, int fee) {
            if (prices.length <= 1) return 0;
            int[] buy = new int[prices.length], sell = new int[prices.length];
            buy[0]=-prices[0];
            for (int i = 1; i<prices.length; i++) {
                buy[i] = Math.max(buy[i - 1], sell[i - 1] - prices[i]); // keep the same as day i-1, or buy from sell status at day i-1
                sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i] - fee); // keep the same as day i-1, or sell from buy status at day i-1
            }
            return sell[prices.length - 1];
        }

  • 0

    @tongzhou2 said in 2 solutions, 2 states DP solutions:

    Start from sell status implies that at day 0, we are just observing stock price, if we buy stock later at day i, the status will transfer to buy status at day i.


Log in to reply
 

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