黑色大气网站,新型产品设计,物联网app开发平台,企业策划309. 买卖股票的最佳时机含冷冻期
买卖股票的最佳时机含冷冻期 分析:
使用动态规划解决 状态表示:
由于有「买入」「可交易」「冷冻期」三个状态#xff0c;因此我们可以选择用三个数组#xff0c;其中#xff1a; ▪ dp[i][0] 表示#xff1a;第 i 天结束后#xff0c… 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(vectorint prices) {int nprices.size();vectorinta(n1);//买入vectorintb(n1);//卖出vectorintc(n1);//冷冻a[0]-prices[0];for(int i1;in;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(vectorint prices, int fee) {int nprices.size();vectorinta(n1);//买入vectorintb(n1);//卖出a[0]-prices[0];for(int i1;in;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(vectorint prices) {const int INF0x3f3f3f3f;int nprices.size();vectorvectorintf(n1,vectorint(3,-INF));//买vectorvectorintg(n1,vectorint(3,-INF));//卖f[0][0]-prices[0];g[0][0]0;for(int i1;in;i){for(int j0;j3;j){f[i][j]max(f[i-1][j],g[i-1][j]-prices[i]);g[i][j]g[i-1][j];if(j-10){g[i][j]max(g[i][j],f[i-1][j-1]prices[i]);}}}int ans0;for(int i0;i3;i){ansmax(ans,g[n-1][i]);}return ans;}
};
