代码随想录算法训练营第四十天 | leetcode：买卖股票的最佳时机,买卖股票的最佳时机II
0 / 0 / 创建于 1年前
_zzh 的个人博客
121. 买卖股票的最佳时机#
解题方法#
思路：与打家劫舍三类似，dp 数组需要记录两个状态，持有股票状态与不持有股票状态，还需要记录天数，所以 dp 需要使用二维数值。
- dp 数组的含义：其中 “持有 / 不持有” 状态不特指当天 “持有 / 不持有”，可能是今天之前 “买入 / 卖出” 到第 i 天的时候还保持 “持有 / 不持有” 状态
- dp[i][0]：第 i 天时，持有股票的状态 ,
- dp[i][1]：第 i 天时，不持有股票的状态
- 确定递推公式：假设初始状态利润为 0；
- dp[i][0] = max(dp[i-1][0], 0-prices[i]);
- dp [i-1][0]：在第 i 天之前就买入了，在第 i 天保持持有状态
- 0-prices [i]：在第 i 天买入的状态，-prices [i] 表示买入的利润，因为只能买入一次，所以第一次买入前，利润肯定是 0，买入之后，就变成 0-prices。
- dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);
- dp [i-1][1]：在第 i 天之前就卖出了，在第 i 天保持不持有状态
- dp [i-1][0] + prices [i]：在第 i 天卖出，dp [i-1][0] 表示第 i 天之前的持有状态，+ prices [i] 表示卖出获得的利润
- 初始化 dp 数组：dp [0][0] 表示第 0 天持有，买入股票，此时利润为 0 - prices [0]; dp [0][1] 表示第 0 天未持有，未买入股票，所以不产生利润，初始化为 0；即：dp[0][0] = -prices[0]； dp[0][1] = 0；
- 遍历顺序：dp [i], 依赖与 dp [i-1], 所以按数组顺序从左到右。
code#
动态规划#
class Solution {
/**
* @param Integer[] $prices
* @return Integer
*/
function maxProfit($prices) {
$dp = [];
//dp[i][0]表示第i天持有股票的状态
//dp[i][1]表示第i天不持有股票的状态
$dp[0][0] = -$prices[0];
$dp[0][1] = 0;
$len = count($prices);
for($i = 1; $i < $len; $i++){
//昨天就买入了与当天买入的最大值
$dp[$i][0] = max($dp[$i-1][0], -$prices[$i]);
//昨天已经卖出与当天卖出的最大值
$dp[$i][1] = max($dp[$i-1][1], $dp[$i-1][0] + $prices[$i]);
}
return $dp[$len - 1][1];
}
}复杂度#
时间复杂度
O (n)，其中 n 为 prices 的长度
空间复杂度
O(n)
贪心#
class Solution {
/**
* @param Integer[] $prices
* @return Integer
*/
function maxProfit($prices) {
$low = PHP_INT_MAX;
$result = 0;
for ($i = 0; $i < count($prices); $i++) {
$low = min($low, $prices[$i]); // 取最左最小价格
$result = max($result, $prices[$i] - $low); // 直接取最大区间利润
//print_r([$low,$result]);
}
return $result;
}
}复杂度#
时间复杂度
O (n)，其中 n 为 prices 的长度
空间复杂度
O(1)
122. 买卖股票的最佳时机 II#
解题方法#
思路：dp 数组需要记录两个状态，持有股票状态与不持有股票状态，还需要记录天数，所以 dp 需要使用二维数值。与买卖股票的最佳时机 I 基本相同，不同的点在于，买卖股票的最佳时机 II 可以多次买入卖出，需要表示第 i 天持有股票状态时，那买入股票前的利润就不一定是 0 了，因为可能之前的买入卖出操作已存在利润，这就是买卖股票的最佳时机 II 与 买卖股票的最佳时机 I 的不同。
- dp 数组的含义：其中 “持有 / 不持有” 状态不特指当天 “持有 / 不持有”，可能是今天之前 “买入 / 卖出” 到第 i 天的时候还保持 “持有 / 不持有” 状态
- dp[i][0]：第 i 天时，持有股票的状态 ,
- dp[i][1]：第 i 天时，不持有股票的状态
- 确定递推公式：假设初始状态利润为 0；
- dp[i][0] = max(dp[i-1][0], dp[i-1][0]-prices[i]);
- dp [i-1][0]：在第 i 天之前就买入了，在第 i 天保持持有状态
- dp [i-1][0]-prices [i]：在第 i 天买入的状态，-prices [i] 表示买入的利润。因为可以买卖多次，所以当前买入不一定是第一次，利润肯定不一定是 0，所以这里相比买卖股票的最佳时机 I 需要变成 dp[i-1][1] 表示第 i 天买入前，不持有股票的状态。dp [i-1][1] - prices [i] 后就能表示当前买入股票的状态。
- dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);
- dp [i-1][1]：在第 i 天之前就卖出了，在第 i 天保持不持有状态
- dp [i-1][0] + prices [i]：在第 i 天卖出，dp [i-1][0] 表示第 i 天之前的持有状态，+ prices [i] 表示卖出获得的利润
- 初始化 dp 数组：dp [0][0] 表示第 0 天持有，买入股票，此时利润为 0 - prices [0]; dp [0][1] 表示第 0 天未持有，未买入股票，所以不产生利润，初始化为 0；即：dp[0][0] = -prices[0]； dp[0][1] = 0；
- 遍历顺序：dp [i], 依赖与 dp [i-1], 所以按数组顺序从左到右。
code#
动态规划#
class Solution {
/**
* @param Integer[] $prices
* @return Integer
*/
function maxProfit($prices) {
$dp = [];
//dp[i][0]表示第i天持有股票的状态
//dp[i][1]表示第i天不持有股票的状态
$dp[0][0] = -$prices[0];
$dp[0][1] = 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] = max($dp[$i - 1][1], $dp[$i - 1][0] + $prices[$i]);
}
return $dp[$len-1][1];
}
}复杂度#
时间复杂度
O(n)
空间复杂度
O(n)
贪心#
class Solution {
/**
* @param Integer[] $prices
* @return Integer
*/
function maxProfit($prices) {
$count = 0;
for($i = 1; $i < count($prices); $i++){
//求利润
$diff = $prices[$i] - $prices[$i-1];
//正利润累加
if($diff > 0){
$count += $diff;
}
}
return $count;
}
}复杂度#
时间复杂度
O(n)
空间复杂度
O(1)
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号
推荐文章：