代码随想录算法训练营第四十二天 | 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]);
}
}
复杂度#
时间复杂度
O (n),其中 n 为 prices 的长度
空间复杂度
O(n)
本作品采用《CC 协议》,转载必须注明作者和本文链接
推荐文章: