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

🟠   🔖  数组 动态规划  🔗 力扣 LeetCode

题目

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:

• After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

Input: prices = [1,2,3,0,2]

Output: 3

Explanation: transactions = [buy, sell, cooldown, buy, sell]

Example 2:

Input: prices = [1]

Output: 0

Constraints:

• 1 <= prices.length <= 5000
• 0 <= prices[i] <= 1000

题目大意

给定一个整数数组 prices，其中第 prices[i] 表示第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: prices = [1,2,3,0,2]

输出: 3

解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

示例 2:

输入: prices = [1]

输出: 0

解题思路

1. 动态规划： 定义一个二维数组 dp，其中 dp[i][0] 表示第 i 天不持有股票时的最大利润， dp[i][1] 表示第 i 天持有股票时的最大利润。

2. 状态转移方程：

   • dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])，表示在第 i 天，不持有股票的最大利润等于前一天不持有股票的最大利润，或者前一天持有股票的最大利润加上今天卖出的利润的最大值。
   • dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])，表示在第 i 天，持有股票的最大利润等于前一天持有股票的最大利润，或者之前两天不持有股票的最大利润减去今天买入的利润的最大值。因为有冷冻期，今天能买入的前提是昨天没有卖出，即前天没有持有股票。

3. 边界条件：

   • 第一天（i == 0）时，dp[0][0] = 0，dp[0][1] = -prices[0]。
   • 第二天（i == 1）时，dp[1][0] = Math.max(0, prices[1] - prices[0])，dp[1][1] = Math.max(-prices[0], -prices[1])。

4. 初始化： 初始化利润为 0。

5. 返回最大利润： 最后返回 dp[n - 1][0]，即最后一天不持有股票的最大利润，因为若最后一天还持有股票没有卖出，收益肯定小于做了一次交易的情况。

复杂度分析

• 时间复杂度: O(n)，遍历整个二维数组，其中 n 是股票价格数组的长度。
• 空间复杂度: O(n)，使用了一个 2 * n 的二维数组来存储中间状态。

代码

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
	const n = prices.length;
	const dp = new Array(n).fill(0).map(() => new Array(2).fill(0));
	for (let i in prices) {
		if (i == 0) {
			dp[0][0] = 0;
			dp[0][1] = -prices[0];
			continue;
		}
		if (i == 1) {
			dp[1][0] = Math.max(0, prices[1] - prices[0]);
			dp[1][1] = Math.max(-prices[0], -prices[1]);
			continue;
		}
		dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
		dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i]);
	}
	return dp[n - 1][0];
};

相关题目

题号	标题	题解	标签	难度
121	买卖股票的最佳时机	[✓]	数组 动态规划
122	买卖股票的最佳时机 II	[✓]	贪心 数组 动态规划