day51
309.最佳买卖股票时机含冷冻期
题目链接：309. 最佳买卖股票时机含冷冻期
1.dp数组的下标及含义
状态1,2是之前的不持有状态分开来算的结果
第i天的状态为j，所剩的最多现金各位$dp[i][j]$;
- $dp[i][0]$：持有股票状态（今天买入股票，或者之前就买入股票没有操作，一直持有）
- $dp[i][1]$：保持卖出股票的状态（两天前就卖出股票，度过了一天冷冻期，或者前一天就是卖出股票的状态没有操作）
- $dp[i][2]$：今天卖出股票（不持有股票，今天卖出股票）
- $dp[i][3]$：今天冷冻期，不可持续只有一天
2.确定递推公式
// 保持前一天持有装填，保持卖出股票状态，冷冻期状态取最大值
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]);
// 保持前一天状态+prices[i]
dp[i][2] = dp[i-1][0]+prices[i];
// 前一天卖出状态
dp[i][3] = dp[i-1][2];
3.初始化
dp[0][0] = -prices[0]; //第一天卖出
dp[0][1] = 0; //非法操作直接赋值0
dp[0][2] = 0; //相当于买入又卖出
dp[0][3] = 0; //非法操作直接赋值0
4.遍历顺序
从前向后遍历
5.打印dp数组
最后取状态2，3，4的最大值即可
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<int>> dp(n,vector<int>(4));
dp[0][0] = -prices[0];
dp[0][1] = 0;
dp[0][2] = 0;
dp[0][3] = 0;
for( int i = 1; i < n; i++){
dp[i][0] = max( dp[i-1][0],max(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] = dp[i-1][0]+prices[i];
dp[i][3] = dp[i-1][2];
}
return max(dp[n-1][1],max(dp[n-1][2],dp[n-1][3]));
}
};
714.买卖股票的最佳时机含手续费
题目链接：714. 买卖股票的最佳时机含手续费
本题和买卖股票的最佳时机II异曲同工，只是加入了手续费，在计算时候直接减即可
第一次做直接AC了，就是注意dp数组初始化时候，$dp[0][1]=0,而不是-2$。这个只是为了方便理解而已。
//参考买卖股票II不难写出如下代码
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
// 时间：O(n)
// 空间：O(n)
// 和买卖股票II一样，只需要加上手续费的操作
int n = prices.size();
vector<vector<int>> dp(n,vector<int>(2));
dp[0][0] = -prices[0];
for( int i = 1; i < n; 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);
}
return max(dp[n-1][0],dp[n-1][1]);
}
};
股票问题总结
