代码随想录算法训练营第四十一天 | leetcode：买卖股票的最佳时机III,买卖股票的最佳时机IV

_zzh 的个人博客 / 26 / 0 / 创建于 1个月前 / 更新于 1个月前

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

解题方法

dp数组的含义：其中 “持有/不持有” 状态不特指当天 “持有/不持有”，可能是今天之前 “买入/卖出” 到第i天的时候还保持 “持有/不持有” 状态

dp[i][0]：第i天时，不操作股票的状态,
dp[i][1]：第i天时，第1次持有股票的状态,
dp[i][2]：第i天时，第1次不持有股票的状态
dp[i][3]：第i天时，第2次持有股票的状态,
dp[i][4]：第i天时，第2次不持有股票的状态

确定递推公式：假设初始状态利润为0；

dp[i][0] = dp[i-0][0]
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])

dp[i-1][1]: 延续上一天状态。
dp[i-1][0] - prices[i]：第i天第1次持有股票（买入），说明上一天是未操作，所以用上一天的状态（dp[i-1][0]）-当天的价格（prices[i]），得到第i天第1次持有股票的状态

dp[i][2] = max(dp[i-1][2], dp[i-1][1] + )

dp[i-1][2]: 延续上一天状态。
dp[i-1][1] - prices[i]：第i天第1次未持有股票（卖出），说明上一天的状态是持有状态，所以用上一天的状态（dp[i-1][1]） + 当天的价格（prices[i]），得到第i天1次未持有股票

dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i])

dp[i-1][3]: 延续上一天状态。
dp[i-1][2] - prices[i]：第i天第2次持有股票（买入），说明上一天是第1次未持有股票（卖出），所以用上一天的状态（dp[i-1][2]）-当天的价格（prices[i]），得到第i天第1次持有股票的状态

dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i])

dp[i-1][4]: 延续上一天状态。
dp[i-1][3] - prices[i]：第i天第2次未持有股票（卖出），说明上一天是第2次持有股票（卖出），所以用上一天的状态（dp[i-1][3]）+ 当天的价格（prices[i]），得到第i天第2次未持有股票的状态

初始化dp数组：

dp[0][0] = 0；第1天未操作的状态
dp[0][1] = -prices[0]; 第1天买入持有的状态
dp[0][2] = 0；第1天买入后卖出未持有的状态
dp[0][3] = -prices[0]; 第1天反复买卖最后持有的状态
dp[0][4] = 0；第1天反复买卖最后未持有的状态

遍历顺序：dp[i],依赖与dp[i-1],所以按数组顺序从左到右。

code

动态规划

class Solution {

    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) {
        $dp = [];
        /**
            tip：根据示例4可以看出 可以当天买入卖出 T+0;
            dp[i][0] : 不操作；
            dp[i][1] : 第一次持有
            dp[i][2] : 第一次卖出
            dp[i][3] : 第二次持有
            dp[i][4] : 第二次卖出
         */
         $dp[0][0] = 0; $dp[0][1] = -$prices[0]; 
         $dp[0][2] = 0; $dp[0][3] = -$prices[0]; $dp[0][4] = 0; 
         $len = count($prices);
         for($i = 1; $i < $len; $i++){
            $dp[$i][0] = $dp[$i-1][0];
            $dp[$i][1] = max($dp[$i-1][1], $dp[$i-1][0] - $prices[$i]);
            $dp[$i][2] = max($dp[$i-1][2], $dp[$i-1][1] + $prices[$i]);
            $dp[$i][3] = max($dp[$i-1][3], $dp[$i-1][2] - $prices[$i]);
            $dp[$i][4] = max($dp[$i-1][4], $dp[$i-1][3] + $prices[$i]);
         }
         return $dp[$len - 1][4];
    }
}

复杂度

时间复杂度

O(n)，其中 n 为 prices 的长度

空间复杂度

O(n)

188. 买卖股票的最佳时机 IV

解题方法

思路：与买卖股票的最佳时机 III唯一的不同就是买卖次数，可以把买卖股票的最佳时机 III只能卖两次的处理抽象成变量j表示即可。

dp数组的含义：其中 “持有/不持有” 状态不特指当天 “持有/不持有”，可能是今天之前 “买入/卖出” 到第i天的时候还保持 “持有/不持有” 状态

dp[i][0]：第i天时，不操作股票的状态,
dp[i][1]：第i天时，第1次持有股票的状态,
dp[i][2]：第i天时，第1次不持有股票的状态
dp[i][3]：第i天时，第2次持有股票的状态,
dp[i][4]：第i天时，第2次不持有股票的状态
dp[i][2k-1]：第i天时，第k次持有股票的状态,
dp[i][2k]：第i天时，第k次不持有股票的状态

确定递推公式：假设初始状态利润为0；

dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j]-prices[i]);

dp[i-1][j+1]：在第i天之前就买入了，在第i天保持持有状态
dp[i-1][j]-prices[i]：在第i天买入的状态，-prices[i]表示买入的利润，因为可以交易k次，所以这里要取第i天之前不持有的状态：dp[i-1][j]。
这里取值为j的原因：本次循环的j,就是上一次的j+2。举个例子：dp[i][3]，要表示当天买入时等于=dp[i-1][2]-prices[i]。当循环到j+1=3的时候，j=2。

dp[i][j+2] = max(dp[i-1][j+2], dp[i-1][j+1] + prices[i]);

dp[i-1][j+2]：在第i天之前就卖出了，在第i天保持不持有状态
dp[i-1][j+1] + prices[i]：在第i天卖出，dp[i-1][j+1]表示第i天之前的持有状态，+ prices[i]表示卖出获得的利润

初始化dp数组：循环第2*k次，当j=单数时，设置为-prices[0],即：从0开始，步进2，dp[0][j+1] = -prices[0]。
遍历顺序：dp[i],依赖与dp[i-1],所以按数组顺序从左到右。

code

动态规划

class Solution {

    /**
     * @param Integer $k
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($k, $prices) {
        /**
            tip：根据示例4可以看出 可以当天买入卖出 T+0;
            dp[i][1] : 第1次持有
            dp[i][2] : 第1次卖出
            dp[i][3] : 第2次持有
            dp[i][4] : 第2次卖出
            .....
            dp[i][2k-1] : 第k次持有
            dp[i][2k]   : 第k次卖出
         */
         $dp = [];
         $len = count($prices);
         //初始化二维数组
         for($i = 0; $i < $len; $i++){
            for($j = 0; $j <= $k*2; $j++){
                $dp[$i][$j] = 0;
            }
         }
         //初始化dp[0]
        for($j = 0; $j < $k*2; $j+=2){
            $dp[0][$j+1] = -$prices[0];
        }
        //求递推数组dp
         for($i = 1; $i < $len; $i++){
            for($j = 0; $j < $k*2; $j+=2){
                $dp[$i][$j+1] = max($dp[$i-1][$j+1], $dp[$i-1][$j] - $prices[$i]);
                $dp[$i][$j+2] = max($dp[$i-1][$j+2], $dp[$i-1][$j+1] + $prices[$i]);
            }
         }
         return $dp[$len - 1][$k*2];
    }
}