简单多状态dp第三弹 leetcode -买卖股票的最佳时机问题
309. 买卖股票的最佳时机含冷冻期
买卖股票的最佳时机含冷冻期
分析:
使用动态规划解决
状态表示:
由于有「买入」「可交易」「冷冻期」三个状态，因此我们可以选择用三个数组，其中：
▪ dp[i][0] 表示：第 i 天结束后，处于「买入」状态，此时的最大利润。
▪ dp[i][1] 表示：第 i 天结束后，处于「可交易」状态，此时的最大利润。
▪ dp[i][2] 表示：第 i 天结束后，处于「冷冻期」状态，此时的最大利润。
状态转移方程:
1.处于买入状态的时候，我们现在有股票，此时不能买股票，只能继续持有股票，或者卖
出股票；
2.处于卖出状态的时候：
如果在冷冻期，不能买入。
如果 不在冷冻期，才能买入。
画出状态图
根据状态图可以得出：
买入->买入：什么都不干
买入->卖出：买入股票
对应代码：a[i]=max(a[i-1],c[i-1]-prices[i-1]);
卖出->卖出：什么都不干
卖出->冷冻期：卖出股票
对应代码：b[i]=max(b[i-1],a[i-1]+prices[i-1]);
冷冻期->冷冻期：什么都不干
冷冻期->买入：冷冻期结束
对应代码：c[i]=max(c[i-1],b[i-1]);
代码：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n=prices.size();
vector<int>a(n+1);//买入
vector<int>b(n+1);//卖出
vector<int>c(n+1);//冷冻
a[0]-=prices[0];
for(int i=1;i<=n;i++)
{
a[i]=max(a[i-1],c[i-1]-prices[i-1]);
b[i]=max(b[i-1],a[i-1]+prices[i-1]);
c[i]=max(c[i-1],b[i-1]);
}
return max(b[n],c[n]);//从卖出和冷冻期中选出最大值，因为买入状态肯定不是最大值，因为还有股票没有卖出。
}
};714. 买卖股票的最佳时机含手续费
买卖股票的最佳时机含手续费
分析:
使用动态规划解决
与 买卖股票的最佳时机含冷冻期 问题相似，我们直接画出状态图写状态方程。
状态图：
买入->买入：什么都不干
买入->卖出：买入股票
对应代码：a[i]=max(a[i-1],c[i-1]-prices[i-1]);
卖出->卖出：什么都不干
卖出->买入：卖出股票并支付手续费
对应代码：b[i]=max(b[i-1],a[i-1]+prices[i-1]-fee);
代码:
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int n=prices.size();
vector<int>a(n+1);//买入
vector<int>b(n+1);//卖出
a[0]-=prices[0];
for(int i=1;i<=n;i++)
{
a[i]=max(a[i-1],b[i-1]-prices[i-1]);
b[i]=max(b[i-1],a[i-1]+prices[i-1]-fee);
}
return b[n];
}
};123. 买卖股票的最佳时机 III
买卖股票的最佳时机 III
状态表示:
这里我们选择比较常用的方式，以某个位置为结尾，结合题目要求，定义一个状态表示：
由于有「买入」「可交易」两个状态，因此我们可以选择用两个数组。但是这道题里面还有交易次
数的限制，因此我们还需要再加上一维，用来表示交易次数。其中：
▪ f[i][j] 表示：第 i 天结束后，完成了 j 次交易，处于「买入」状态，此时的最大利
润；
▪ g[i][j] 表示：第 i 天结束后，完成了 j 次交易，处于「卖出」状态，此时的最大利
润。
状态转移方程:
A.对于 f[i][j] ，我们有两种情况到这个状态：
1. 在 i - 1 天的时候，交易了 j 次，处于「买入」状态，第 i 天啥也不干即可。此时最
大利润为： f[i - 1][j] ；
2. 在 i - 1 天的时候，交易了 j 次，处于「卖出」状态，第 i 天的时候把股票买了。此
时的最大利润为： g[i - 1][j] - prices[i] 。
综上，我们要的是「最大利润」，因此是两者的最大值： f[i][j] = max(f[i - 1][j],
g[i - 1][j] - prices[i]) 。
B.对于 g[i][j] ，我们也有两种情况可以到达这个状态：
1.在 i - 1 天的时候，交易了 j 次，处于「卖出」状态，第 i 天啥也不干即可。此时的
最大利润为： g[i - 1][j] ；
2.在 i - 1 天的时候，交易了 j - 1 次，处于「买入」状态，第 i 天把股票卖了，然
后就完成了 j 比交易。此时的最大利润为： f[i - 1][j - 1] + prices[i] 。但
是这个状态不一定存在，要先判断一下。综上，我们要的是最大利润，因此状态转移方程为：
g[i][j] = g[i - 1][j];
if(j >= 1) g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
代码:
class Solution {
public:
int maxProfit(vector<int>& prices) {
const int INF=0x3f3f3f3f;
int n=prices.size();
vector<vector<int>>f(n+1,vector<int>(3,-INF));//买
vector<vector<int>>g(n+1,vector<int>(3,-INF));//卖
f[0][0]=-prices[0];
g[0][0]=0;
for(int i=1;i<n;i++)
{
for(int j=0;j<3;j++)
{
f[i][j]=max(f[i-1][j],g[i-1][j]-prices[i]);
g[i][j]=g[i-1][j];
if(j-1>=0)
{
g[i][j]=max(g[i][j],f[i-1][j-1]+prices[i]);
}
}
}
int ans=0;
for(int i=0;i<3;i++)
{
ans=max(ans,g[n-1][i]);
}
return ans;
}
}; 