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

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

解题方法#

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

dp[i][0]：第 i 天时，持有 / 买入 ,
dp[i][1]：第 i 天时，保持卖出状态 ,
dp[i][2]：第 i 天时，卖出股票这个动作
dp[i][3]：第 i 天时，冷冻期 ,

确定递推公式：假设初始状态利润为 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]：冷冻期前一天是卖出状态的保持

初始化 dp 数组：

dp[0][0] = -prices[0]；
dp [0][1] = 0; 非法状态，第一天不存在这种状态，根据递推公式可得初始化为 0
dp[0][2] = 0；
dp [0][3] = 0; 非法状态，第一天不存在这种状态，根据递推公式可得初始化为 0

遍历顺序：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. 买卖股票的最佳时机含手续费 #

解题方法#

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

dp[i][0]：第 i 天时，持有股票的状态 ,
dp[i][1]：第 i 天时，未持有股票的状态 ,

确定递推公式：假设初始状态利润为 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: 扣除手续费

初始化 dp 数组：$dp[0][0] = -$prices[0]；$dp[0][1] = 0；

因为当前卖出需要手续费，当天买卖是纯亏，不考虑当天买卖的情况，所以 $dp [0][1] = 0；

遍历顺序：dp [i], 依赖与 dp [i-1], 所以按数组顺序从左到右。
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]);
    }
}