原文链接
题目描述：
给定一个数组， 它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来计算你所能获取的最大利润，最多可完成两笔交易，且不能同时参与多笔交易，即再次购买之前必须出售掉之前的股票。
问题分析：
得到该问题的动态转移方程并不难：
dp[k, i]=max(dp[k, i −1], prices[i]−prices[j]+dp[k −1, j −1]), j=[0..i −1]
对于k笔交易，在第i天：
• 如果我们选择不交易，那么收益跟前一天保持一致为dp[k, i-1]
• 如果我们在j天买了股票(j=[0..i-1])，然后在第i天卖出了，那么我们的收益为 prices[i]−prices[j]+dp[k−1, j −1].
实际上j可以等于i，当j=i时，prices[i]−prices[j]+dp[k−1, j]= dp[k −1, i],看上去像是减少了一次交易机会。
我看到有些人在使用公式dp[k, i]=ma x(dp[k, i −1], prices[i]−prices[j]+dp[k−i, j])，而不是dp[k −i, j −1].实际上这没有多大意义，如果股票在第j天被买入了，那么上一次交易的总收益应该与第j-1天的收益一样。当然，基于这种考虑的动态转移方程也是正确的，因为如果股票在第j天被出售了然后在当天又买回来了，这种情况与第j天没有进行交易是一样的。
所以，最直观的实现方式如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public int maxProfitDp(int[] prices) {
if(prices.length == 0) return 0;
int[][] dp = new int[3][prices.length];
for(int k = 1; k <= 2; k++) {
for(int i = 1; i < prices.length; i++) {
int min = prices[0];
for(int j = 1; j <= i; j++) {
min = Math.min(min, prices[j] - dp[k - 1][j - 1]);
}
dp[k][i] = Math.max(dp[k][i - 1], prices[i] - min);
}
}
return dp[2][prices.length - 1];
}
|
时间复杂度为O(kn^2),空间复杂度为O(kn).
在上述代码中，min被重复计算了，我们可以进行优化：
1
2
3
4
5
6
7
8
9
10
11
12
| public int maxProfitDp(int[] prices) {
if(prices.length == 0) return 0;
int[][] dp = new int[3][prices.length];
for(int k = 1; k <= 2; k++) {
int min = prices[0];
for(int i = 1; i < prices.length; i++) {
min = Math.min(min, prices[i] - dp[k - 1][i - 1]);
dp[k][i] = Math.max(dp[k][i - 1], prices[i] - min);
}
}
return dp[2][prices.length - 1];
}
|
时间复杂度为O(kn),空间复杂度为O(kn).
如果我们将两个for循环进行交换：
1
2
3
4
5
6
7
8
9
10
11
12
13
| public int maxProfitDp(int[] prices) {
if(prices.length == 0) return 0;
int[][] dp = new int[3][prices.length];
int[] min = new int[3];
Arrays.fill(min, prices[0]);
for(int i = 1; i < prices.length; i++) {
for(int k = 1; k <= 2; k++) {
min[k] = Math.min(min[k], prices[i] - dp[k - 1][i - 1]);
dp[k][i] = Math.max(dp[k, i - 1], prices[i] - min[k]);
}
}
return dp[2][prices.length - 1];
}
|
我们需要在每次交易时都保存最小值min，所以会保存k个min。
我们发现二维数组的第二维i的值仅取决于前一个i-1的值，所以我们可以进行纬度压缩。(我们也可以压缩第一纬度k，因为第k个位置也是仅取决于第k-1个位置。但是两个维度不能同时压缩)
1
2
3
4
5
6
7
8
9
10
11
12
13
| public int maxProfitDp(int[] prices) {
if(prices.length == 0) return 0;
int[] dp = new int[3];
int[] min = new int[3];
Arrays.fill(min, prices[0]);
for(int i = 1; i < prices.length; i++) {
for(int k = 1; k <= 2; k++) {
min[k] = Math.min(min[k], prices[i] - dp[k - 1]);
dp[k] = Math.max(dp[k], prices[i] - min[k]);
}
}
return dp[2];
}
|
此时时间复杂度为O(kn),空间复杂度为O(k).
在这道题中，k=2.我们可以将数组直接用变量代替
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public int maxProfitDp(int[] prices) {
int buy1 = Integer.MAX_VALUE;
int buy2 = Integer.MAX_VALUE;
int sell1 = 0;
int sell2 = 0;
for(int i = 0; i < prices.length; i++) {
buy1 = Math.min(buy1, prices[i]);
sell1 = Math.max(sell1, prices[i] - buy1);
buy2 = Math.min(buy2, prices[i] - sell1);
sell2 = Math.max(sell2, prices[i] - buy2);
}
return sell2;
}
|
我们也可以用其他的方式来解释上面的代码。每一天我们都尽可能地买入最低价股票，并且尽可能地用最高价卖出。对于第二次交易，我们把第一次交易的盈利放入第二次交易的成本中(做差，第二次的成本减第一次的盈利prices[i]−sell1)，那么我们第二次交易的的盈利就是两次交易的盈利。