代码随想录算法训练营第三十九天-121买卖股票的最佳时机、122买卖股票的最佳时机II、123买卖股票的最佳时机III

前言
状态：121 直接看的解析。122 可以写出。123 看了部分解析（主要是 dp 的定义那块）。
更新

1	24-06-27 初始记录

初步题解

121 买卖股票的最佳时机

题目链接：(https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/)：可以进行一笔交易

确定 dp[i] 的含义：dp[i][0] 表示第 i 天持有股票所得最多现金，dp[i][1] 表示第 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]);。（分为两种情况，当前持有/不持有）
dp 数组的初始化：dp[0][0] = -prices[0]; dp[0][1] = 0;。还有一点要注意：不持有股票状态所得金钱一定比持有股票状态得到的多！
遍历顺序：从前向后遍历。
打印 dp 数组（用于 debug）

public int maxProfit(int[] prices) {  
    // `dp[i][0]` 表示第 i 天持有股票所得最多现金，`dp[i][1]` 表示第 i 天不持有股票所得最多现金。  
    int[][] dp = new int[prices.length][2];  
  
    // 初始化  
    dp[0][0] = -prices[0];  
    dp[0][1] = 0;  
  
    for (int i = 1; i < prices.length; i++) {  
        // 1. 求 dp[i][0]: 前一天也持有就为 dp[i - 1][0]，前一天不持有就为 -prices[i]        
        dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);  
        // 2. 求 dp[i][1]: 前一天也不持有就为 dp[i - 1][1]，前一天持有就为 dp[i - 1][0] + prices[i]        
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);  
    }  
  
    System.out.println(Arrays.deepToString(dp));  

	// 手中不持有股票时，利润才会最大
    return dp[prices.length - 1][1];
}

122 买卖股票的最佳时机 II

题目链接：(https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii)：可以进行多笔交易

确定 dp[i] 的含义：dp[i][0] 表示第 i 天持有股票所得最多现金，dp[i][1] 表示第 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]);。（与上一题的唯一区别为 dp[i][0] 的推导公式，由于可以持续买入卖出，当天持有的价格为前一天不持有的价格 - 当天价格）
dp 数组的初始化：dp[0][0] = -prices[0]; dp[0][1] = 0;。还有一点要注意：不持有股票状态所得金钱一定比持有股票状态得到的多！
遍历顺序：从前向后遍历。
打印 dp 数组（用于 debug）

public int maxProfit(int[] prices) {  
    // `dp[i][0]` 表示第 i 天持有股票所得最多现金，`dp[i][1]` 表示第 i 天不持有股票所得最多现金。  
    int[][] dp = new int[prices.length][2];  
  
    // 初始化  
    dp[0][0] = -prices[0];  
    dp[0][1] = 0;  
  
    for (int i = 1; i < prices.length; i++) {  
        // 1. 求 dp[i][0]: 前一天也持有就为 dp[i - 1][0]，前一天不持有就为 dp[i - 1][1] - prices[i]        
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);  
        // 2. 求 dp[i][1]: 前一天也不持有就为 dp[i - 1][1]，前一天持有就为 dp[i - 1][0] + prices[i]        
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);  
    }  
  
    System.out.println(Arrays.deepToString(dp));  
  
    return dp[prices.length - 1][1];
}

123 买卖股票的最佳时机 III

题目链接：(https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/)：可以进行两笔交易

确定 dp[i] 的含义：当天的状态一共有 5 种：没有操作，不计入。dp[i][0] 表示第 i 天第一次持有股票所得最多现金，dp[i][1] 表示第 i 天第一次不持有股票所得最多现金，dp[i][2] 表示第 i 天第二次持有股票所得最多现金，dp[i][2] 表示第 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]); dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] - prices[i]); dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] + prices[i]);。
dp 数组的初始化：dp[0][0] = -prices[0]; dp[0][2] = -prices[0];。
遍历顺序：从前向后遍历。
打印 dp 数组（用于 debug）

public static int maxProfit(int[] prices) {  
    // `dp[i][0]` 表示第 i 天第一次持有股票所得最多现金，`dp[i][1]` 表示第 i 天第一次不持有股票所得最多现金，`dp[i][2]` 表示第 i 天第二次持有股票所得最多现金，`dp[i][2]` 表示第 i 天第二次不持有股票所得最多现金 
    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++) {  
        // 1. 求 dp[i][0]: 前一天也持有就为 dp[i - 1][0]，前一天不持有就为 -prices[i]        
        dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);  
        // 2. 求 dp[i][1]: 前一天也不持有就为 dp[i - 1][1]，前一天持有就为 dp[i - 1][0] + prices[i]        
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);  
        // 3. 求 dp[i][2]: 前一天也持有为 dp[i - 1][2]，前一天不持有就为 dp[i - 1][1] - prices[i]        
        dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] - prices[i]);  
        // 4. 求 dp[i][3]: 前一天也不持有为 dp[i - 1][3]，前一天持有就为 dp[i - 1][2] + prices[i]        
        dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] + prices[i]);  
    }  
  
    System.out.println(Arrays.deepToString(dp));  
  
    return dp[prices.length - 1][3];  
}

看解析

121 买卖股票的最佳时机

解析：(https://programmercarl.com/0121.买卖股票的最佳时机.html)

补充贪心算法的思路：如果第 i 天卖出股票，则最大利润为 (该天的股价 - 前面天数中最小的股价)，然后与已知的最大利润比较，如果大于则更新当前最大利润的值。

/**  
 * 贪心解法  
 */  
public int maxProfit(int[] prices) {  
    int minPrice = Integer.MAX_VALUE;  
    int maxProfit = 0;  
  
    for (int price : prices) {  
        minPrice = Math.min(price, minPrice);  
        maxProfit = Math.max(maxProfit, price - minPrice);  
    }  
  
    return maxProfit;  
}

122 买卖股票的最佳时机 II

解析：(https://programmercarl.com/0122.买卖股票的最佳时机II（动态规划）.html)

123 买卖股票的最佳时机 III

解析：(https://programmercarl.com/0123.买卖股票的最佳时机III)

版本二：（不做要求）

public int maxProfit(int[] prices) {
    int[] dp = new int[4]; 
    // 存储两次交易的状态就行了
    // dp[0]代表第一次交易的买入
    dp[0] = -prices[0];
    // dp[1]代表第一次交易的卖出
    dp[1] = 0;
    // dp[2]代表第二次交易的买入
    dp[2] = -prices[0];
    // dp[3]代表第二次交易的卖出
    dp[3] = 0;
    for(int i = 1; i <= prices.length; i++){
        // 要么保持不变，要么没有就买，有了就卖
        dp[0] = Math.max(dp[0], -prices[i-1]);
        dp[1] = Math.max(dp[1], dp[0]+prices[i-1]);
        // 这已经是第二次交易了，所以得加上前一次交易卖出去的收获
        dp[2] = Math.max(dp[2], dp[1]-prices[i-1]);
        dp[3] = Math.max(dp[3], dp[2]+ prices[i-1]);
    }
    return dp[3];
}