代码随想录算法训练营day41

1.买卖股票的最佳时机

1.1 题目

. - 力扣（LeetCode）

1.2 题解

class Solution {
public:
	int maxProfit(vector<int>& prices)
	{
		//定义dp数组，dp[i][0]表示第i天不持有股票身上的现金，dp[i][1]表示第i天持有股票身上的现金
		vector<vector<int>> dp(prices.size(), vector<int>(2, 0));


		//初始化
		dp[0][0] = 0;
		dp[0][1] = -prices[0];

		//开始遍历
		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],-prices[i]);
		}

		return dp[prices.size()-1][0];
	}
};

2.买卖股票的最佳时机II

2.1 题目

. - 力扣（LeetCode）

2.2 题解

class Solution
{
public:
    int maxProfit(vector<int>& prices)
    {
		//确定dp数组，dp[i][0]表示第i天手上没有股票身上的钱，dp[i][1]表示第i天有股票身上的钱
		vector<vector<int>> dp(prices.size(), vector<int>(2, 0));

		//确定递推公式
		// 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]);

		//初始化
		dp[0][0] = 0;
		dp[0][1] = -prices[0];

		//开始遍历
		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]);
		}

		return dp[prices.size() - 1][0];
    }
};

3.买卖股票的最佳时机

3.1 题目

. - 力扣（LeetCode）

3.2 题解

class Solution {
public:
	int maxProfit(vector<int>& prices) 
	{
		int len = prices.size();
		//定义dp数组
		vector<vector<int>> dp(len, vector<int>(5, 0));
		//dp数组有5个状态
		//dp[i][0]表示第i天不进行操作
		//dp[i][1]表示第i天第一次持有股票
		//dp[i][2]表示第i天第一次不持有股票
		//dp[i][3]表示第i天第二次持有股票
		//dp[i][4]表示第i天第二次不持有股票

		//确定递推逻辑
		/*dp[i][0] = dp[i - 1][0];
		dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
		dp[i][2] = max(dp[i - 1][2], dp[i-1][1] + prices[i]);
		dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
		dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);*/

		//初始化
		dp[0][0] = 0;
		dp[0][1] = -prices[0];
		dp[0][2] = 0;
		dp[0][3] = -prices[0];
		dp[0][4] = 0;
		
		//开始遍历
		for (int i = 1; i < len; i++)
		{
			dp[i][0] = dp[i - 1][0];
			dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
			dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
			dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
			dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
		}
		return dp[len - 1][4];
	}
};