江门公司网站建设域名三天更换一次

一、最佳买卖股票时机含冷冻期

题目描述:

思路和想法：

 这道题相较于之前的题目，注重对状态的分析，这里分为四个状态。

（1）状态一，买入状态 dp[i][0]

• 操作一：前一天就是持有状态（状态一）dp[i - 1][0]
• 操作二：今天买入，两种情况①前一天是冷冻期（状态四），dp[i - 1][3] - prices[i]
• ②前一天是保持卖出股票的状态dp[i - 1][1] - prices[i]

（2）状态二，保持卖出股票的状态 dp[i][1]  （还没卖出）

• 操作一：前一天就是状态二 dp[i - 1][1]
• 操作二：前一天是冷冻期（状态四） dp[i - 1][3]

（3）状态三，达到今天卖出的状态 dp[i - 1][0] + prices[i]

（4）状态四，冷冻期 dp[i - 1][2]

#include<vector>
using namespace std;
class Solution {
public:int maxProfit(vector<int>& prices) {//四个状态 买入，保持卖出、今天就卖出以及冷冻vector<vector<int>> dp(prices.size(),vector<int>(4,0));if(prices.size() == 0) return 0;dp[0][0] = -prices[0];for (int i = 1; i < prices.size(); 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[prices.size() - 1][3], max(dp[prices.size() - 1][2],dp[prices.size() - 1][1]));}
};

二、最佳买卖股票时机含手续费

题目描述：

 思路和想法：

        这里的话，就两个状态，买入和保持卖出

（1）买入：dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);

（2）卖出：dp[i][1] = max(dp[i - 1][1], dp[i -1][0] + prices[i] - fee);

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {vector<vector<int>> dp(prices.size(),vector<int>(2,0));dp[0][0] = -prices[0];//0表示买入，1表示卖出for (int i = 1; i < prices.size(); 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[prices.size() - 1][1], dp[prices.size() - 1][0]);}
};