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

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

解题方法

  1. 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次不持有股票的状态
  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次未持有股票的状态
  3. 初始化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天反复买卖最后未持有的状态
  4. 遍历顺序: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表示即可。

  1. 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次不持有股票的状态
  2. 确定递推公式:假设初始状态利润为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]表示卖出获得的利润
  3. 初始化dp数组:循环第2*k次,当j=单数时,设置为-prices[0],即:从0开始,步进2,dp[0][j+1] = -prices[0]。
  4. 遍历顺序: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];
    }
}

复杂度

时间复杂度

O(n * k),其中 n 为 prices 的长度

空间复杂度

O(n * k)

本作品采用《CC 协议》,转载必须注明作者和本文链接
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!