来源Leetcode第123题买股票的最佳时机III
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
状态机模板
解法来自题解
采用一个3维数组dp[n][k][2]来标记股票的交易情况。
比如说 dp[3][2][1] 的含义就是：今天是第三天，我现在手上持有着股票，至今最多进行 2 次交易。再比如 dp[2][3][0] 的含义：今天是第二天，我现在手上没有持有股票，至今最多进行 3 次交易。
我们想求的最终答案是 dp[n - 1][K][0]，即最后一天，最多允许 K 次交易，最多获得多少利润。
基础框架:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15base case：
dp[-1][k][0] = dp[i][0][0] = 0
//因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0 。
dp[-1][k][1] = dp[i][0][1] = -infinity
还没开始的时候，是不可能持有股票的，用负无穷表示这种不可能。
状态转移方程：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
//解释：今天我没有持有股票，有两种可能：
要么是我昨天就没有持有，然后今天选择 rest，所以我今天还是没有持有；
要么是我昨天持有股票，但是今天我 sell 了，所以我今天没有持有股票了。
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
//解释：今天我持有着股票，有两种可能：
要么我昨天就持有着股票，然后今天选择 rest，所以我今天还持有着股票；
要么我昨天本没有持有，但今天我选择 buy，所以今天我就持有股票了。
那么构建的代码如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21public int maxProfit(int[] prices) {
if(prices.length == 0 || prices.length < 2)
return 0;
int max_k = 2;
int n = prices.length;
int[][][] dp = new int[n][max_k + 1][2];
for (int i = 0; i < n; i++) {
for (int k = max_k; k >= 1; k--) {
if (i == 0) { /*处理 base case */
dp[i][k][0] = 0;
dp[i][k][1] = - 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 - 1][k - 1][0] - prices[i]);
}
}
// 穷举了 n × max_k × 2 个状态，正确。
return dp[n - 1][max_k][0];
}
状态机精简
用s0代表初始状态，初始时钱是 0。dp_i_1_1代表第一次买入后当前的钱，dp_i_1_0代表第一次卖出后当前的前，dp_i_2_1代表第二次买入后当前的钱，dp_i_2_0代表第二次卖出后当前的钱。
然后我们只需要更新每天的这四个状态即可。
代码如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14public int maxProfit(int[] prices) {
if(prices.length == 0 || prices.length < 2)
return 0;
//进行初始化，第一天 dp_i_1_1 将股票买入，其他状态全部初始化为最小值
int dp_i_1_1 = -prices[0],dp_i_1_0 = Integer.MIN_VALUE,dp_i_2_1 = Integer.MIN_VALUE,dp_i_2_0 = Integer.MIN_VALUE;
for(int i=1;i<prices.length;++i) {
dp_i_1_1 = Math.max(dp_i_1_1, -prices[i]); //买入价格更低的股
dp_i_1_0 = Math.max(dp_i_1_0, dp_i_1_1+prices[i]); //卖出当前股，或者不操作
dp_i_2_1 = Math.max(dp_i_2_1, dp_i_1_0-prices[i]); //第二次买入，或者不操作
dp_i_2_0 = Math.max(dp_i_2_0, dp_i_2_1+prices[i]); //第二次卖出，或者不操作
}
return Math.max(0,dp_i_2_0);
}