【算法日志】动态规划刷题：股票买卖附加问题(day42)

代码随想录刷题60Day

目录

前言

含冷冻期的股票买卖最佳时期

含手续费的股票买卖最佳时期

前言

今天的股票买卖问题会附加一些条件，但总体难度不大。

含冷冻期的股票买卖最佳时期

该问题难点在于对几个状态进行解构并写出相应的状态转移方程。

	int maxProfit(vector<int>& prices) 
	{
		int size = prices.size();
		vector<vector<int>> dp(size, vector<int>(4, 0));
		dp[0][0] = -prices[0];
		// 0: 买入（持有）  1：卖出（未持有）  2：可购入（未持有）  3：不可操作（冷冻期, 未持有）
		for (int i = 1; i < size; ++i)
		{
			dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][2], dp[i - 1][3]) - prices[i]);
			dp[i][1] = dp[i - 1][0] + prices[i];
			dp[i][2] = max(dp[i - 1][2], dp[i - 1][3]);
			dp[i][3] = dp[i - 1][1];
		}
		return max(dp[size - 1][1], max(dp[size - 1][2], dp[size - 1][3]));
	}

含手续费的股票买卖最佳时期

	int maxProfit(vector<int>& prices, int fee)
	{
		int size = prices.size();
		vector<vector<int>> dp(2, vector<int>(2, 0));
		dp[0][0] = -prices[0] - fee;
		for (int i = 1; i < size; ++i)
		{
			dp[i % 2][0] = max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] - prices[i] - fee);
			dp[i % 2][1] = max(dp[(i - 1) % 2][1], dp[(i - 1) % 2][0] + prices[i]);
		}
		return dp[(size - 1) % 2][1];
	}