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

缘起

继续沉迷股票~ leetcode 309. 最佳买卖股票时机含冷冻期

分析

1
2
3
4
5
6
7
8
9
10
11
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​

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

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:

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

本题在【1】的基础上加入了冷冻期这一概念. 即我们如果假设 a[1,…,n]是prices的一阶差分序列的话, 则

如果a[i] 是后一个片段和的起点的话, 则前一个片段最多到 i-3

1
2
3
4
5
6
令 dp[i] 是以 a[i]为结尾的最大结果, dpp[i]是a[1,..,i]的最大结果. 则
我们有
dp[i] = max{dpp[i-k-2]+sum[i-k+1,...,i]}, 1<=k<=i, 对于k=i,i-1, i-2, dp[i-k-2]取0就好
dpp[i] = max{dp[1],...,dp[i]}, 1<=i<=n, 这时显然的.
最后的答案是 dpp[n], 初始值是 dp[1]  =a[1]
即本题是双dp方程

其中 sum[i-k+1,…,i] 是 差分序列 a 的 i-k+1,…,i 这段长k的片段和. 可以O(1)处理出来. 所以纵观上面的dp方程, 我们不难知道计算的顺序应该是dp[1]作为初始值, 然后先计算dp, 然后O(1)更新dpp, 注意到 dp的计算依赖dpp[i-3],…,dpp[1], 所以不用担心, 一定能计算出来的. 复杂度是O(n^2)的.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
	int maxProfit(vector<int>& prices) 
	{
		int n = prices.size();
		if (n<=1)
		{
			return 0;
		}
		s[0] = 0;
		for (int i = 1;i<n;i++)
		{
			a[i] = prices[i]-prices[i-1];
			s[i] = s[i-1]+a[i];
		}
		--n; // 处理出一阶差分序列a[1,...,n]
		if (n==1)
		{
			return max(a[1], 0);
		}
		dp[1] = a[1];
		dpp[1] = max(a[1], 0);
		for (int i = 2;i<=n; i++)
		{
			dp[i] = a[i]; // k=1的时候
			for (int k = 1; k<=i; k++)
			{
				dp[i] = max(dp[i], (i-k-2>0?dpp[i-k-2]:0)+s[i]-s[i-k]);
			} // 计算dp[i]
			dpp[i] = max(dpp[i-1], dp[i]); // 计算dpp
		}
		return dpp[n];
	}

	const static int maxn = 50005;
	int a[maxn],dp[maxn], dpp[maxn], s[maxn]; // s是a的部分和序列

};

ac情况

1
2
3
4
5
6
7
8
9
10
11
12
13
执行结果：
通过
显示详情
执行用时 :
92 ms
, 在所有 cpp 提交中击败了
5.08%
的用户
内存消耗 :
9.4 MB
, 在所有 cpp 提交中击败了
69.31%
的用户

这种时间太慢了~ 因为是O(n^2)的算法. 有没有更好的算法呢? 我参考了 99°兄的博客~

考虑三种状态 s0, s1, s2, 分别表示是没有买入、买入后等待卖出、卖出后 三种状态. 其中 s0和s2的区别在于由于题目的冷冻期规则, 所以s2状态一定要进入s0状态, 而不能直接进入s1状态. 所以我们知道了这三种状态的转换规则

令 s0[i]、s1[i]、s2[i] 分别是第i天处于这个状态（即s0[i]处于的是状态s0,s1[i]处于的状态是s1, s2[i]处于的状态是s2）的最大收益. 则

  1. 能到达s0[i]的方式有 从s2[i-1]到达或者从 s0[i-1]状态到达, 即 s0[i] = max(s0[i-1], s2[i-1])
  2. 能到达s1[i]的方式有 从 s0[i-1]到达或者从 s1[i-1] 到达. 但是如果是从 s0[i-1]到达的话, 则其实就是花费了 prices[i] 买进股票, 所以 s1[i] = max(s0[i-1]-prices[i], s1[i-1])
  3. 能到达s2[i]的方式只有s1[i-1]+price[i], 所以 s2[i] = s1[i-1]+prices[i]

真的给万能的DP跪了! 本题是三状态dp, 即参与dp的变量不止一个而是3个. 下面考虑初始值

  1. s0[0]是第0天处于没有买入的状态, 则最大收益显然是0.

  2. s1[0]是第0天处于买入状态的最大收益, 显然是-prices[0].

  3. s2[0]是第0天处于卖出后的状态. 最大收益显然是0（即表示第0天买入之后就立刻卖出掉了）

而答案显然是 max(s0[n-1], s2[n-1])（显然最后不可能处于买入等待卖出的状态, 那还不如不买）. 即本题通过巧妙的多状态dp, 将原本复杂的问题处理的如此优雅~ 复杂度是O(n)的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
	int maxProfit(vector<int>& prices) 
	{
		int n = prices.size();
		if (!n)
		{
			return 0;
		}
		s0[0] = 0, s1[0] = -prices[0], s2[0] = 0;
		for (int i =1;i<n;i++)
		{
			s0[i] = max(s0[i-1], s2[i-1]);
			s1[i] = max(s0[i-1]-prices[i], s1[i-1]);
			s2[i] = s1[i-1]+prices[i];
		}
		return max(s0[n-1], s2[n-1]);
	}
	const static int maxn =50005;
	int s0[maxn], s1[maxn], s2[maxn];
};

ac情况

1
2
3
4
5
6
7
8
9
10
11
12
13
执行结果：
通过
显示详情
执行用时 :
12 ms
, 在所有 cpp 提交中击败了
19.72%
的用户
内存消耗 :
9 MB
, 在所有 cpp 提交中击败了
73.02%
的用户

速度比之前的O(n^2)算法快了很多~

参考

【1】https://yfsyfs.github.io/2019/10/23/leetcode-122-%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BA-II/