Leecode learning notes

• Stock issues - You can only buy it once

Because you can only buy it once , So the definition of dp[i][0] The first i Days holding shares , Can only be -price[i], There can be no accumulation of profits , namely dp[i - 1][1]-prices[i]

class Solution {
    
    public int maxProfit(int[] prices) {
    
        int[][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
    
            dp[i][0] = Math.max(dp[i - 1][0], - prices[i]);
            dp[i][1] = Math.max(dp[i  - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[prices.length - 1][1];

    }
}

• Stock issues - You can buy many times

You can buy many times here , therefore dp[i][0] Holding the profits of holding stocks every day can consider the previous profits , namely dp[i - 1][1] - prices[i]（ There was no profit from holding shares the previous day - The stock price of the day , This indicates that the previous transaction has ended , The rest is the profit from not holding shares the day before ）

class Solution {
    
    public int maxProfit(int[] prices) {
    
        // int res = 0;
        // for (int i = 1; i < prices.length; i++) {
    
        // res += Math.max(prices[i] - prices[i - 1], 0);// Only collect positive profits 
        // }
        // return res;

        int[][] dp = new int[prices.length][2];
        dp[0][0] = - prices[0];
        dp[0][1] = 0;

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

• Stock issues - Bought it twice

I bought this twice , In fact, it is similar to the first stock problem , You can't buy or sell many times , Just like the recurrence of the first case , Just add the status of the second purchase

class Solution {
    
    public int maxProfit(int[] prices) {
    
        int[][] dp = new int[prices.length][4];
        
        dp[0][0] = -prices[0];
        dp[0][2] = -prices[0];

        for (int i = 1; i < prices.length; i++) {
    
            // The first i The profit of holding shares for the first time 
            dp[i][0] = Math.max(dp[i - 1][0], - prices[i]);
            // The first i For the first time, the profit of not holding shares 
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
            // The first i The profit of holding shares for the second time in the day 
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] - prices[i]);
            // The first i For the second time in the day, the profit of not holding shares 
            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] + prices[i]);            
        }

        return dp[prices.length - 1][3];

        

    }
}