代码随想录算法训练营第四十二天 | leetcode：买卖股票的最佳时机含冷冻期,买卖股票的最佳时机含手续费
0 / 2 / 创建于 11个月前
_zzh 的个人博客
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 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号
所以这个能让我不亏吗？