AlgoPressAppearance
0309-最佳买卖股票时机含冷冻期
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown
给定一个整数数组，其中第i个元素代表了第i天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。 示例:
输入: [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
基本思路
第二天高于第一天就可以卖出，卖出影响下一天买入【跳掉下一格】
参考代码
csharp
public class Solution {
public int MaxProfit(int[] prices) {
if(prices.Length == 0){
return 0;
}
int [,] dp = new int[prices.Length,3];
int n = prices.Length - 1;
// dp[i][0]: 手上持有股票的最大收益
// dp[i][1]: 手上不持有股票，并且处于冷冻期中的累计最大收益
// dp[i][2]: 手上不持有股票，并且不在冷冻期中的累计最大收益
dp[0,0] = -prices[0];
for(int i=1; i<=n; i++){
dp[i,0] = Math.Max(dp[i-1,0],dp[i-1,2] - prices[i]);
dp[i,1] = dp[i-1,0] + prices[i];
dp[i,2] = Math.Max(dp[i-1,1],dp[i-1,2]);
}
return Math.Max(dp[n,1],dp[n,2]);
}
}
优化空间
csharp
public class Solution {
public int MaxProfit(int[] prices) {
if(prices.Length == 0){
return 0;
}
int n = prices.Length - 1;
int hold = -prices[0]; // 手上持有股票的最大收益
int noAndCold = 0; // 手上不持有股票，并且处于冷冻期中的累计最大收益
int noAndNotCold = 0; // 手上不持有股票，并且不在冷冻期中的累计最大收益
for(int i=1; i<=n; i++){
int newHold = Math.Max(hold, noAndNotCold - prices[i]);
int newNoAndCold = hold + prices[i];
int newNoAndNotCold = Math.Max(noAndCold, noAndNotCold);
hold = newHold;
noAndCold = newNoAndCold;
noAndNotCold = newNoAndNotCold;
}
return Math.Max(noAndCold,noAndNotCold);
}
}
复习：2022-04-02
csharp
public class Solution {
public int MaxProfit(int[] prices) {
//动态规划
// dp[i,0] 表示手上持有股票的最大收益
// dp[i,1] 表示不持有股票，处于冷冻期的最大收益
// dp[i,2] 表示不持有股票，处于非冷冻期的最大收益
int[,] dp = new int[prices.Length, 3];
dp[0,0] = -prices[0];
dp[0,1] = 0;
dp[0,2] = 0;
for(int i=1; i<prices.Length; i++){
//今天持有股票 = 要么昨天持有股票，或者昨天没有持有(且非冷冻)，今天持有了
dp[i,0] = Math.Max(dp[i-1,0],dp[i-1,2] - prices[i]);
//今天不持有(冷冻期) = 昨天持有的最大价值 + 今天的最大价格(注意:虽然也可以包含昨天不持有的情况，但是显然只有持有然后卖掉收益才最大)
//dp[i,1] = Math.Max(dp[i-1,0] + prices[i],Math.Max(dp[i-1,1],dp[i-1,2]));
dp[i,1] = dp[i-1,0] + prices[i];
//今天不持有：非冷冻
dp[i,2] = Math.Max(dp[i-1,1],dp[i-1,2]);
}
return Math.Max(dp[prices.Length-1,1],dp[prices.Length-1,2]);
}
}
复习: 20220515 还是没太懂
csharp
public class Solution {
public int MaxProfit(int[] prices) {
//定义dp
//dp[i,0] 持有股票的最大收益
//dp[i,1] 不持有股票且是冷冻期的最大收益
//dp[i,2] 不持有股票且不是冷冻期的最大收益
int n = prices.Length;
int[,] dp = new int[n,3];
dp[0,0] = -prices[0]; //
for(int i=1; i<prices.Length; i++){
dp[i,0] = Math.Max(dp[i-1,0], dp[i-1,2]-prices[i]); //持有股票(昨天就持有，或着昨天是冷冻期，今天买入)
dp[i,1] = prices[i] + dp[i-1,0]; // 昨天持有，今天卖掉
dp[i,2] = Math.Max(dp[i-1,2],dp[i-1,1]); //昨天不持有，或者昨天持有 选大的
}
return Math.Max(dp[n-1,1],dp[n-1,2]);
}
}
复习: 20220630
csharp
public class Solution {
public int MaxProfit(int[] prices) {
//动态规划
int n = prices.Length;
int[,] dp = new int[n,3];
// dp[i,0] 表示第 i 天持有股票的利润
// dp[i,1] 表示第 i 天不持有股票的利润(刚卖掉/冷冻期)
// dp[i,2] 表示第 i 天不持有股票的利润(非冷冻期)
dp[0,0] = -prices[0];
for(int i=1; i<n; i++){
dp[i,0] = Math.Max(dp[i-1,0], dp[i-1,2] -prices[i]); //前一天就持有，或者当天持有
dp[i,1] = dp[i-1,0] + prices[i]; //
dp[i,2] = Math.Max(dp[i-1,1],dp[i-1,2]);
}
return Math.Max(dp[n-1,1],dp[n-1,2]);
}
}