本文主要是介绍代码训练营第53天：动态规划part12｜leetcode309买卖股票的最佳时期含冷静期｜leetcode714买卖股票的最佳时机含手续费，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
leetcode309：买卖股票的最佳时机含冷冻期
文章讲解：leletcode309
leetcode714：买卖股票的最佳时机含手续费
文章讲解：leetcode714
目录
1，leetcode309 买卖股票的最佳时机含冷冻期
2，leetcode714 买卖股票的最佳时机含手续费
1，leetcode309 买卖股票的最佳时机含冷冻期
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][1], dp[n - 1][2]));}
};我的理解是，股票问题其实是个自动机问题，每一步递推实际上是自动机的状态变化过程
具体可以区分出如下四个状态：
- 状态一：持有股票状态（今天买入股票，或者是之前就买入了股票然后没有操作，一直持有）
- 不持有股票状态，这里就有两种卖出股票状态
- 状态二：保持卖出股票的状态（两天前就卖出了股票，度过一天冷冻期。或者是前一天就是卖出股票状态，一直没操作）
- 状态三：今天卖出股票
- 状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！
实际上这个状态转移图一出来，逐个状态分析即可。
2，leetcode714 买卖股票的最佳时机含手续费
其实在之前的递推中，只要加入在购买的时候减去手续费就可以了。但是在这种情况下[1]就不一定是最大的，需要两个状态求max
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]);}
};这篇关于代码训练营第53天：动态规划part12｜leetcode309买卖股票的最佳时期含冷静期｜leetcode714买卖股票的最佳时机含手续费的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
