代码随想录算法训练营第四十二天 | 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]);
    }
}