题解 | #股票（两次交易）#

• dp数组及下标含义
  • dp[i][j]：记录第i天结束时处于状态j时现金收益
  • i：天数
  • j：状态
    • j = 0：处于未交易状态
    • j = 1：处于第一次买入的状态
    • j = 2：处于第一次卖出的状态
    • j = 3：处于第二次买入的状态
    • j = 4：处于第二次卖出的状态
• 递推公式
  • 第i天结束时依旧未交易的现金收益：0
  • 第i天结束时处于第一次买入状态的现金收益
    • 第i-1天就处于第一次买入状态，第i天休息：dp[i - 1][1]
    • 第i-1天就处于未交易状态，第i天进行第一次买入：-prices[i]
  • 第i天结束时处于第一次卖出状态的现金收益
    • 第i-1天就处于第一次卖出状态，第i天休息：dp[i - 1][2]
    • 第i-1天就处于第一次买入状态，第i天进行第一次卖出：dp[i][1] + prices[i]
  • 第i天结束时处于第二次买入状态的现金收益
    • 第i-1天就处于第二次买入状态，第i天休息：dp[i - 1][3]
    • 第i-1天就处于第一次卖出状态，第i天进行第二次买入：dp[i][2] - prices[i]
  • 第i天结束时第二次卖出状态的现金收益
    • 第i-1天就处于第二次卖出状态，第i天休息：dp[i - 1][4]
    • 第i-1天就处于第二次买入状态，第i天进行第二次卖出：dp[i][3] + prices[i]

class Solution {
    public int maxProfit(int[] prices) {
        //1. dp数组及下标的含义：dp[天数][状态]
        int[][] dp = new int[prices.length][5];

        //2. 初始化
        dp[0][1] = -prices[0];
        dp[0][3] = -prices[0];

        //3. 遍历方向
        for(int i = 1; i < prices.length; ++i){
            //4. 递推公式
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
            dp[i][2] = Math.max(dp[i - 1][2], dp[i][1] + prices[i]);
            dp[i][3] = Math.max(dp[i - 1][3], dp[i][2] - prices[i]);
            dp[i][4] = Math.max(dp[i - 1][4], dp[i][3] + prices[i]);
        }

        return dp[prices.length - 1][4];
    }
}