05 August 2008
dp[i][j][k] - 第i天还可以交易k次，不买股票时的最大收益 dp[i][j][1] - 第i天还可以交易k次，买股票时的最大收益
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
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= 1) {
return 0;
}
int len = prices.length;
int[][][] dp = new int[len][2][2];
for (int i = 0; i < len; i++) {
for (int k = 1; k >= 1; k--) { // k天的冷冻期，这里k是1，标识至少可以交易一次，无需这个内层循环
// 两个if处理初始化
if (i == 0) {
dp[i][k][0] = 0;
dp[i][k][1] = -prices[0];
continue;
}
if (i == 1) {
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k][0] - prices[i]);
continue;
}
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 2][k][0] - prices[i]);
}
}
return dp[len - 1][1][0];
}
}
也可以将cooldown的标识合并到第二维中去，少一个维度，例如
dp[i][0]: 第i天不买股票，并且处于冷冻期中的累计最大收益
dp[i][1]: 第i天不买股票，并且不处于冷冻期中的累计最大收益
dp[i][2]: 第i天买股票时的最大收益
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(int[] prices) {
int len = prices.length;
if (len <= 1) {
return 0;
}
int[][] dp = new int[len][3];
dp[0][0] = 0;
dp[0][1] = -1 * prices[0];
dp[0][2] = 0;
for (int i = 1; i < len; i++) { //从[1]...[n-1]
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
dp[i][2] = dp[i - 1][1] + prices[i];
}
return Math.max(dp[len - 1][0], dp[len - 1][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
class Solution {
public int maxProfit(int[] prices) {
if (prices.length <= 1) {
return 0;
}
//第一天持有的最大收益是-prices[0]
int oldHave = -prices[0];
//第一天不持有，而且什么也不做的最大收益是0
int oldNotHaveButDoNothing = 0;
//第一天卖出的最大收益是0
int oldSell = 0;
int nowSell,nowHave,nowNotHaveButDoNothing=0;
for (int i = 0; i < prices.length; i++) {
//今天卖出
nowSell = prices[i] + oldHave;
//今天没有而且今天没有进行任何操作=昨天没有而且没有进行操作,或者昨天卖了,今天没有任何操作
nowNotHaveButDoNothing = Math.max(oldNotHaveButDoNothing, oldSell);
//今天有=昨天就有,或者今天买入
nowHave = Math.max(oldHave, oldNotHaveButDoNothing - prices[i]);
oldHave = nowHave;
oldNotHaveButDoNothing = nowNotHaveButDoNothing;
oldSell = nowSell;
}
return Math.max(oldSell, oldNotHaveButDoNothing);
}
}