309 最佳买卖股票时机含冷冻期
思路：可以定义一个二维数组dp，其中dp[i][j]表示第i天，状态为j时的最大利润，状态j表示以下四种情况：
j=0：表示持有股票时的最大利润；
j=1：表示不持有股票，处于冷冻期时的最大利润；
j=2：表示不持有股票，且不在冷冻期时的最大利润；
j=3：表示不持有股票，且当天卖出股票时的最大利润。
具体实现时，可以采用以下思路：
对于第一天，如果买入股票，则dp[0][0]=-prices[0]；
对于其它天，可以分以下两种情况讨论：
如果在第i天持有股票，则dp[i][0]=max(dp[i-1][0], dp[i-1][2]-prices[i], dp[i-1][3]-prices[i])；
如果在第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]。
最后，最大利润即为max(dp[n-1][0], dp[n-1][1], dp[n-1][2], dp[n-1][3])。
1.动态规划
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if(n == 0) return 0;
vector<vector<int>> dp(n, vector<int> (4, 0));
dp[0][0] -= prices[0];
for(int i = 1; i < n; i++){
dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3] - prices[i], dp[i - 1][1] - 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][3], max(dp[n - 1][2], dp[n - 1][1]));
}
};
714 买卖股票的最佳时机含手续费
思路：首先定义一个二维的vector dp，大小为n×2，其中n是prices的长度。dp[i][0]表示第i天持有股票的最大收益，dp[i][1]表示第i天不持有股票的最大收益。
接下来，初始化dp[0][0]为-prices[0]，即第一天买入股票，初始化其他元素为0。
然后，从第二天开始遍历prices，对于第i天，计算dp[i][0]和dp[i][1]，其中：
dp[i][0]表示第i天持有股票的最大收益，有两种情况：不操作（dp[i - 1][0]）或者卖出（dp[i - 1][1] - prices[i]），选择两者中的较大值。
dp[i][1]表示第i天不持有股票的最大收益，同样有两种情况：不操作（dp[i - 1][1]）或者买入（dp[i - 1][0] + prices[i] - fee），选择两者中的较大值。
最后，返回dp[n - 1][0]和dp[n - 1][1]中的较大值，即最大收益。
1.动态规划
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int n = prices.size();
vector<vector<int>> dp(n, vector<int> (2, 0));
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]);
}
};
