代码随想录算法训练营第四十二天 | leetcode:买卖股票的最佳时机含冷冻期,买卖股票的最佳时机含手续费

309. 买卖股票的最佳时机含冷冻期

解题方法

  1. dp数组的含义:其中 “持有/不持有” 状态不特指当天 “持有/不持有”,可能是今天之前 “买入/卖出” 到第i天的时候还保持 “持有/不持有” 状态
    • dp[i][0]:第i天时,持有/买入,
    • dp[i][1]:第i天时,保持卖出状态,
    • dp[i][2]:第i天时,卖出股票这个动作
    • dp[i][3]:第i天时,冷冻期,
  2. 确定递推公式:假设初始状态利润为0;
    • dp[i][0] = max(dp[i-1][0],dp[i-1][1]-prices[i],dp[i-1][3]-prices[i])
      • dp[i-1][0]:保持前一天状态,
      • dp[i-1][1]-prices[i]:前一天是保持卖出状态时的买入
      • dp[i-1][3]-prices[i]:前一天是冷冻期的买入
    • dp[i][1] = max(dp[i-1][1], dp[i-1][3])
      • dp[i-1][1]:保持前一天状态
      • dp[i-1][3]:前一天是冷冻期的状态
    • dp[i][2] = max(dp[i-1][2], dp[i-1][0] + prices[i])
      • dp[i-1][2]:保持前一天状态
      • dp[i-1][0] + prices[i]:前一天是持有股票时,卖出的状态
    • dp[i][3] = dp[i-1][2]
      • dp[i-1][2]:冷冻期前一天是卖出状态的保持
  3. 初始化dp数组:
    • dp[0][0] = -prices[0];
    • dp[0][1] = 0;非法状态,第一天不存在这种状态,根据递推公式可得初始化为0
    • dp[0][2] = 0;
    • dp[0][3] = 0;非法状态,第一天不存在这种状态,根据递推公式可得初始化为0
  4. 遍历顺序:dp[i],依赖与dp[i-1],所以按数组顺序从左到右。

code

动态规划

class Solution {

    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) {
        $dp=[];
        $dp[0][0] = -$prices[0]; $dp[0][1] = 0;
        $dp[0][2] = 0; $dp[0][3] = 0;
        $len = count($prices);
        for($i = 1; $i < $len; $i++){
            $dp[$i][0] = max($dp[$i-1][0], $dp[$i-1][1] - $prices[$i], $dp[$i-1][3] - $prices[$i]);
            $dp[$i][1] = max($dp[$i-1][1], $dp[$i-1][3]);
            $dp[$i][2] = max($dp[$i-1][2], $dp[$i-1][0] + $prices[$i]);
            $dp[$i][3] = $dp[$i-1][2];
        }
        //返回三个不持有状态的最大值
        return max($dp[$len-1][1], $dp[$len-1][2], $dp[$len-1][3]);
    }
}

复杂度

时间复杂度

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

空间复杂度

O(n)

714. 买卖股票的最佳时机含手续费

解题方法

  1. dp数组的含义:其中 “持有/不持有” 状态不特指当天 “持有/不持有”,可能是今天之前 “买入/卖出” 到第i天的时候还保持 “持有/不持有” 状态
    • dp[i][0]:第i天时,持有股票的状态,
    • dp[i][1]:第i天时,未持有股票的状态,
  2. 确定递推公式:假设初始状态利润为0;
    • dp[i][0] = max(dp[i-1][0],dp[i-1][1] - prices[i]);;
      • dp[i-1][0]:在第i天之前就买入了,在第i天保持持有状态
      • dp[i-1][1] - prices[i]:在第i天买入的状态,-prices[i]表示买入的利润,因为可以交易k次,所以这里要取第i天之前不持有的状态:dp[i-1][1]。
    • dp[i][1] = max(dp[i-1][1],dp[i-1][0] + prices[i] - fee);;
      • dp[i-1][j+2]:在第i天之前就卖出了,在第i天保持不持有状态
      • dp[i-1][0] + prices[i] - fee:在第i天卖出,dp[i-1][0]表示第i天之前的持有状态,+ prices[i]表示卖出获得的利润 ,-fee:扣除手续费
  3. 初始化dp数组:$dp[0][0] = -$prices[0];$dp[0][1] = 0;
    • 因为当前卖出需要手续费,当天买卖是纯亏,不考虑当天买卖的情况,所以$dp[0][1] = 0;
  4. 遍历顺序:dp[i],依赖与dp[i-1],所以按数组顺序从左到右。
  5. tips: 当无论怎么买卖都是负数时,不操作即是最大利润
    • 例如:prices = [9,8,7,1,2],fee = 3。最大利润就是0;

code

动态规划

class Solution {

    /**
     * @param Integer[] $prices
     * @param Integer $fee
     * @return Integer
     */
    function maxProfit($prices, $fee) {
        $dp = [];
        $len = count($prices);
        for($i = 0; $i < $len; $i++){
            $dp[$i][0] = 0;  
            $dp[$i][1] = 0;    
        }
        $dp[0][0] = -$prices[0];
        //$dp[0][1] = -$fee;
        for($i = 1; $i < $len; $i++){
            $dp[$i][0] = max($dp[$i-1][0], $dp[$i-1][1] - $prices[$i]);
            $dp[$i][1] = max($dp[$i-1][1], $dp[$i-1][0] + $prices[$i] - $fee);
        }
        //print_r($dp);
        return max($dp[$len-1][0], $dp[$len-1][1]);
    }
}

复杂度

时间复杂度

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

空间复杂度

O(n)

本作品采用《CC 协议》,转载必须注明作者和本文链接
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
《G01 Go 实战入门》
从零开始带你一步步开发一个 Go 博客项目,让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。
讨论数量: 2

所以这个能让我不亏吗?

4周前 评论
_zzh (楼主) 4周前

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