代码随想录算法训练营第四十一天 | leetcode：买卖股票的最佳时机III,买卖股票的最佳时机IV
0 / 0 / 创建于 11个月前 /
_zzh 的个人博客
123. 买卖股票的最佳时机 III
解题方法
- dp数组的含义：其中 “持有/不持有” 状态不特指当天 “持有/不持有”，可能是今天之前 “买入/卖出” 到第i天的时候还保持 “持有/不持有” 状态
- dp[i][0]：第i天时，不操作股票的状态,
- dp[i][1]：第i天时，第1次持有股票的状态,
- dp[i][2]：第i天时，第1次不持有股票的状态
- dp[i][3]：第i天时，第2次持有股票的状态,
- dp[i][4]：第i天时，第2次不持有股票的状态
- 确定递推公式：假设初始状态利润为0；
- dp[i][0] = dp[i-0][0]
- dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
- dp[i-1][1]: 延续上一天状态。
- dp[i-1][0] - prices[i]：第i天第1次持有股票（买入），说明上一天是未操作，所以用上一天的状态（dp[i-1][0]）-当天的价格（prices[i]），得到第i天第1次持有股票的状态
- dp[i][2] = max(dp[i-1][2], dp[i-1][1] + )
- dp[i-1][2]: 延续上一天状态。
- dp[i-1][1] - prices[i]：第i天第1次未持有股票（卖出），说明上一天的状态是持有状态，所以用上一天的状态（dp[i-1][1]） + 当天的价格（prices[i]），得到第i天1次未持有股票
- dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i])
- dp[i-1][3]: 延续上一天状态。
- dp[i-1][2] - prices[i]：第i天第2次持有股票（买入），说明上一天是第1次未持有股票（卖出），所以用上一天的状态（dp[i-1][2]）-当天的价格（prices[i]），得到第i天第1次持有股票的状态
- dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i])
- dp[i-1][4]: 延续上一天状态。
- dp[i-1][3] - prices[i]：第i天第2次未持有股票（卖出），说明上一天是第2次持有股票（卖出），所以用上一天的状态（dp[i-1][3]）+ 当天的价格（prices[i]），得到第i天第2次未持有股票的状态
- 初始化dp数组：
- dp[0][0] = 0；第1天未操作的状态
- dp[0][1] = -prices[0]; 第1天买入持有的状态
- dp[0][2] = 0；第1天买入后卖出未持有的状态
- dp[0][3] = -prices[0]; 第1天反复买卖最后持有的状态
- dp[0][4] = 0；第1天反复买卖最后未持有的状态
- 遍历顺序：dp[i],依赖与dp[i-1],所以按数组顺序从左到右。
code
动态规划
class Solution {
/**
* @param Integer[] $prices
* @return Integer
*/
function maxProfit($prices) {
$dp = [];
/**
tip：根据示例4可以看出 可以当天买入卖出 T+0;
dp[i][0] : 不操作；
dp[i][1] : 第一次持有
dp[i][2] : 第一次卖出
dp[i][3] : 第二次持有
dp[i][4] : 第二次卖出
*/
$dp[0][0] = 0; $dp[0][1] = -$prices[0];
$dp[0][2] = 0; $dp[0][3] = -$prices[0]; $dp[0][4] = 0;
$len = count($prices);
for($i = 1; $i < $len; $i++){
$dp[$i][0] = $dp[$i-1][0];
$dp[$i][1] = max($dp[$i-1][1], $dp[$i-1][0] - $prices[$i]);
$dp[$i][2] = max($dp[$i-1][2], $dp[$i-1][1] + $prices[$i]);
$dp[$i][3] = max($dp[$i-1][3], $dp[$i-1][2] - $prices[$i]);
$dp[$i][4] = max($dp[$i-1][4], $dp[$i-1][3] + $prices[$i]);
}
return $dp[$len - 1][4];
}
}复杂度
时间复杂度
O(n)，其中 n 为 prices 的长度
空间复杂度
O(n)
188. 买卖股票的最佳时机 IV
解题方法
思路：与 买卖股票的最佳时机 III唯一的不同就是买卖次数，可以把买卖股票的最佳时机 III只能卖两次的处理抽象成变量j表示即可。
- dp数组的含义：其中 “持有/不持有” 状态不特指当天 “持有/不持有”，可能是今天之前 “买入/卖出” 到第i天的时候还保持 “持有/不持有” 状态
- dp[i][0]：第i天时，不操作股票的状态,
- dp[i][1]：第i天时，第1次持有股票的状态,
- dp[i][2]：第i天时，第1次不持有股票的状态
- dp[i][3]：第i天时，第2次持有股票的状态,
- dp[i][4]：第i天时，第2次不持有股票的状态
- dp[i][2k-1]：第i天时，第k次持有股票的状态,
- dp[i][2k]：第i天时，第k次不持有股票的状态
- 确定递推公式：假设初始状态利润为0；
- dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j]-prices[i]);
- dp[i-1][j+1]：在第i天之前就买入了，在第i天保持持有状态
- dp[i-1][j]-prices[i]：在第i天买入的状态，-prices[i]表示买入的利润，因为可以交易k次，所以这里要取第i天之前不持有的状态：dp[i-1][j]。
这里取值为j的原因：本次循环的j,就是上一次的j+2。举个例子：dp[i][3]，要表示当天买入时等于=dp[i-1][2]-prices[i]。当循环到j+1=3的时候，j=2。- dp[i][j+2] = max(dp[i-1][j+2], dp[i-1][j+1] + prices[i]);
- dp[i-1][j+2]：在第i天之前就卖出了，在第i天保持不持有状态
- dp[i-1][j+1] + prices[i]：在第i天卖出，dp[i-1][j+1]表示第i天之前的持有状态，+ prices[i]表示卖出获得的利润
- 初始化dp数组：循环第2*k次，当j=单数时，设置为-prices[0],即：从0开始，步进2，dp[0][j+1] = -prices[0]。
- 遍历顺序：dp[i],依赖与dp[i-1],所以按数组顺序从左到右。
code
动态规划
class Solution {
/**
* @param Integer $k
* @param Integer[] $prices
* @return Integer
*/
function maxProfit($k, $prices) {
/**
tip：根据示例4可以看出 可以当天买入卖出 T+0;
dp[i][1] : 第1次持有
dp[i][2] : 第1次卖出
dp[i][3] : 第2次持有
dp[i][4] : 第2次卖出
.....
dp[i][2k-1] : 第k次持有
dp[i][2k] : 第k次卖出
*/
$dp = [];
$len = count($prices);
//初始化二维数组
for($i = 0; $i < $len; $i++){
for($j = 0; $j <= $k*2; $j++){
$dp[$i][$j] = 0;
}
}
//初始化dp[0]
for($j = 0; $j < $k*2; $j+=2){
$dp[0][$j+1] = -$prices[0];
}
//求递推数组dp
for($i = 1; $i < $len; $i++){
for($j = 0; $j < $k*2; $j+=2){
$dp[$i][$j+1] = max($dp[$i-1][$j+1], $dp[$i-1][$j] - $prices[$i]);
$dp[$i][$j+2] = max($dp[$i-1][$j+2], $dp[$i-1][$j+1] + $prices[$i]);
}
}
return $dp[$len - 1][$k*2];
}
}复杂度
时间复杂度
O(n * k)，其中 n 为 prices 的长度
空间复杂度
O(n * k)
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号