123. 买卖股票的最佳时机 III

题意：

解题思路：

思路：
状态: dp[i][k][0]表示第i天进行了k次交易，目前不持有股票；dp[i][k][1]表示第i天进行了k次交易，目前持有股票.
状态转移方程:
1、当天进行了k次交易，并不持有股票的最大收益为两种情况取大者：一、前一天交易了k次本身也不持有股票；二、前一天进行了k次交易，并持有股票，今天卖了。交易发生在当天，所以前一天的交易次数是k, 不是k - 1。
dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
2、当天进行了k次交易，并持有股票的最大收益为两种情况取大者：一、前一天交易了k次本身持有股票；二、前一天进行了最多k - 1次交易，并不持有股票，当天买入了。当天还能买入，说明之前交易次数没有达到k次。
dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);

PHP代码实现：

class Solution {
    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) {
        return $this->maxProfitO1($prices); 
        if (empty($prices)) return 0;
        $dp = [];
        $maxK = 2;
        for ($i = 0; $i < count($prices); $i++) {
            for ($k = $maxK; $k >= 1; $k--) {
                if ($i == 0) {
                    $dp[$i][$k][0] = 0;
                    $dp[$i][$k][1] = -$prices[$i];
                    continue;
                }
                $dp[$i][$k][0] = max($dp[$i - 1][$k][0], $dp[$i - 1][$k][1] + $prices[$i]);
                $dp[$i][$k][1] = max($dp[$i - 1][$k][1], $dp[$i - 1][$k - 1][0] - $prices[$i]);
            }
        }
        return $dp[count($prices) - 1][$maxK][0];
    }
    function maxProfitO1($prices) {
        if (empty($prices)) return 0;
        /**
         * $dp[$i][2][0] = max($dp[$i - 1][2][0], $dp[$i - 1][2][1] + $prices[$i]);
         * $dp[$i][2][1] = max($dp[$i - 1][2][1], $dp[$i - 1][1][0] - $prices[$i]);
         *
         * $dp[$i][1][0] = max($dp[$i - 1][1][0], $dp[$i - 1][1][1] + $prices[$i]);
         * $dp[$i][1][1] = max($dp[$i - 1][1][1], $dp[$i - 1][0][0] - $prices[$i]);
         */
        //对照上面做等价变形
        $dp_i00 = 0;
        $dp_i10 = 0;
        $dp_i20 = 0;
        $dp_i21 = PHP_INT_MIN;
        $dp_i11 = PHP_INT_MIN;
        for ($i = 0; $i < count($prices); $i++) {
            $dp_i20 = max($dp_i20, $dp_i21+ $prices[$i]);
            $dp_i21 = max($dp_i21, $dp_i10- $prices[$i]);
            $dp_i10 = max($dp_i10, $dp_i11+ $prices[$i]);
            $dp_i11 = max($dp_i11, $dp_i00-$prices[$i]);
        }
        return $dp_i20;
    }
}

GO代码实现：

func maxProfit(prices []int) int {
    dp_i00, dp_i10, dp_i20 := 0, 0, 0
    dp_i11, dp_i21 := math.MinInt64, math.MinInt64
    for _, v := range prices {
        dp_i20 = max(dp_i20, dp_i21 + v)
        dp_i21 = max(dp_i21, dp_i10 - v)
        dp_i10 = max(dp_i10, dp_i11 + v)
        dp_i11 = max(dp_i11, dp_i00 - v)
    }
    return dp_i20
}
func max(a, b int) int {
    if a < b {
        return b 
    }
    return a
}