309. 最佳买卖股票时机含冷冻期
思路：
这道题的思路和之前的题目思路是类似的。dp[i][j]:第i天的j状态下，持有的最大现金为dp[i][j]。递推关系：这里的j有四种情况：j为持有状态、j为不持有的保持卖出状态、j为不持有当天卖出状态、j为冷冻期。当j=0为持有状态时，可以是保持持有dp[i-1][0]，可以是未持有状态后买入的（保持未持有dp[i-1][1]-prices[i]或者冷冻期dp[i-1][3]-prices[i]）,三者取最大值。当j=1为不持有的保持卖出状态，可以是保持先一天的状态dp[i-1][1]，也可以是冷冻期后依旧不买入dp[i-1][3]，二者取最大值。当j=2为不持有当天卖出状态时，前一天的状态一定是持有状态dp[i-1][0]+prices[i]。当j=3为冷冻期时，前一天一定是不持有当天卖出状态dp[i-1][2]。初始值：dp[0][0]=-prices[0]、dp[0][1]=0、dp[0][2]=0。遍历顺序：从小到大。
代码:
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len=prices.size();
if(len==0) return 0;
vector<vector<int>> dp(len,vector<int>(4,0));
dp[0][0]=-prices[0];
dp[0][1]=0;
dp[0][2]=0;
for(int i=1;i<len;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[len - 1][3], max(dp[len - 1][1], dp[len - 1][2]));
}
};
714. 买卖股票的最佳时机含手续费
思路：
这道题的思路和第122题一致，只是在卖出时增加了手续费。dp[i][j]:在第i天情况j下持有的最大现金数为dp[i][j]。递推关系：当j=0为持有股票时，可以是前一天就持有股票dp[i-1][0]，也可以是当天才买入dp[i-1][1]-prices[i]，二者取最大。当j=1为不持有股票时，可以是继续前一天的不持有股票dp[i-1][1]，也可以是当天卖出股票，此时要收取手续费dp[i-1][0]+prices[i]-fee，二者取最大值。初始化：dp[0][0]=-prices[0],dp[0][1]=0。遍历顺序：从小到大。
代码：
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int len=prices.size();
if(len==0)return 0;
vector<vector<int>> dp(len,vector<int>(2,0));
dp[0][0]=-prices[0];
for(int 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]-fee);
}
return dp[len-1][1];
}
};
