C++ day51 买卖股票最佳时期
题目1：309 买卖股票的最佳时机含冷冻期
题目链接：买卖股票的最佳时机含冷冻期
对题目的理解
prices[i]表示第i天股票的价格，尽可能多地完成更多的交易，不能同时进行多笔交易，卖出股票后，第二天无法买入股票（冷冻期是1天），计算最大利润
动态规划
动规五部曲
1）dp数组及下标i的含义
状态1：dp[i][0] 第i天持有股票的状态最大现金
状态2：dp[i][1] 第i天保持股票卖出的状态，冷冻期之后最大现金
状态3：dp[i][2] 第i天具体卖出股票的状态，冷冻期的前一天最大现金
状态4：dp[i][3] 第i天冷冻期的状态最大现金
最终求解：dp[prices.size()-1][1] dp[prices.size()-1][2] dp[prices.size()-1][3]的
2）递推公式
dp[i][0] = dp[i-1][0] 前一天持有股票
买入股票:前一天是冷冻期；前一天保持卖出股票状态
dp[i][0] = dp[i-1][3]-prices[i]
dp[i][0] = dp[i-1][1]-prices[i]
dp[i][0] = max(dp[i-1][0],dp[i-1][3]-prices[i],dp[i-1][1]-prices[i])
dp[i][1] = dp[i-1][1] 冷冻期之后一直保持股票卖出的状态
dp[i][1] = dp[i-1][3] 冷冻期的状态的下一天
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] 前一天是具体卖出股票的状态
3）dp数组初始化
dp[0][0]=-prices[0]
dp[0][1]的状态是一个非法状态，看递推公式中需要初始化为多少，dp[1][0]=dp[0][1]-prices[1],所以将dp[0][1]初始化成0(当天买当天卖)
dp[1][0] = dp[0][3]-prices[1] 所以将dp[0][3]初始化为0
同理将dp[0][2]初始化为0
4）遍历顺序
根据递推公式，dp[i] 依赖于 dp[i-1]，从小到大遍历
5）打印dp数组
代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
//定义dp数组
vector<vector<int>> dp(prices.size(),vector<int>(4,0));
//初始化dp数组
dp[0][0] = -prices[0];
//递推
for(int i=1;i<prices.size();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[prices.size()-1][1],max(dp[prices.size()-1][2],dp[prices.size()-1][3]));
}
};- 时间复杂度：O(n)
- 空间复杂度：O(n)
题目2：714 买卖股票的最佳时机含手续费
题目链接：买卖股票的最佳时机含手续费·
对题目的理解
prices[i]表示第i天的股票价格 fee代表交易股票的手续费，每笔交易都需要附手续费，可以无限次的进行交易，不能同时进行多次交易，返回利润的最大值。
动态规划
动规五部曲
1）dp数组及下标i的含义
dp[i][0]：第i天持有股票的最大现金数
dp[i][1]：第i天不持有股票的最大现金数
最后求解：dp[prices.size()-1][1]
2）递推公式
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)，不持有股票可以分为两种情况，一种是一直不持有，还有一种是前一天持有股票，那么，今天卖出，就达到了不持有的情况,同时需要减去手续费
3）dp数组初始化
根据递推公式，初始化dp[0][0]和dp[0][1]，
dp[0][0]代表第i天持有股票的最大现金数，dp[1][0]=dp[0][0]，那么为-prices[0]
dp[1][0]代表第i天不持有股票的最大现金数 dp[1][1]=dp[0][1] 那么第一天一定是买或者不买股票，所以不持有股票的最大现金数是0
4）遍历顺序
根据递推公式，从小到大遍历 for(i=1;i<prices.size();i++)注意i从1开始遍历
5）打印dp数组
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
//定义dp数组
vector<vector<int>> dp(prices.size(),vector<int>(2,0));
//初始化dp数组
dp[0][0] = -prices[0];
for(int i=1;i<prices.size();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 dp[prices.size()-1][1];
}
};- 时间复杂度：O(n)
- 空间复杂度：O(n)