给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成?两笔?交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
关键在于至多买卖两次，这意味着可以买卖一次，可以买卖两次，也可以不买卖。
类比买卖一次有持有和不持有两种状态
买卖两次有五种状态
1. dp数组以及下标含义
dp[len][5]
dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金。
需要注意：dp[i][1]，表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票，这是很多同学容易陷入的误区。
因为是持有的状态，不是说状态的改变在当天发生的，也可能是之前发生，这次维持这种状态
2. 递推公式
除了没有操作是直接维持原有状态
其他的都有两个选择，改变状态的操作在当天发生/维持前一天的当前状态
dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1]);
dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2]);
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
3. 数组初始化
第0天没有操作，即：dp[0][0] = 0;
第0天做第一次买入的操作，dp[0][1] = -prices[0];
第0天做第一次卖出的操作，可以理解当天买入，当天卖出，所以dp[0][2] = 0;
第0天第二次买入操作，第二次买入依赖于第一次卖出的状态，其实相当于第0天第一次买入了，第一次卖出了，然后再买入一次（第二次买入），那么现在手头上没有现金，只要买入，现金就做相应的减少。
所以第二次买入操作，初始化为：dp[0][3] = -prices[0];
同理第二次卖出初始化dp[0][4] = 0;
其实题目问的是至多买两次，如果只有一天的情况，不作买卖（利润为0）就是最大利润，但是这种情况其实也就相当于，第两次买卖就在当天（不产生利润与亏损）
所以在返回最后结果时，可以直接返回dp[len-1][4]。最优结果不买卖相当于有两次时当天买卖，最有结果就买卖一次相当于第二次当天买卖了结果。
4. 遍历方向：由递推公式可知，递推公式的计算只需要用到dp[i-1][j] 的数据，从后往前遍历就好了
与上题的区别就是两次买卖，和k次买卖
题目要求是至多有K笔交易，那么j的范围就定义为 2 * k + 1 就可以了。
最大的区别就是这里要类比j为奇数是买，偶数是卖的状态。
for (int j = 0; j < 2 * k - 1; j += 2) {
dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}遍历奇偶数的一种方法如上，可以每次+2
初始化
由上题同理可以推出dp[0][j]当j为奇数的时候都初始化为 -prices[0]
// 版本二: 二维 dp数组
class Solution {
public int maxProfit(int k, int[] prices) {
if (prices.length == 0) return 0;
// [天数][股票状态]
// 股票状态: 奇数表示第 k 次交易持有/买入, 偶数表示第 k 次交易不持有/卖出, 0 表示没有操作
int len = prices.length;
int[][] dp = new int[len][k*2 + 1];
// dp数组的初始化, 与版本一同理
for (int i = 1; i < k*2; i += 2) {
dp[0][i] = -prices[0];
}
for (int i = 1; i < len; i++) {
for (int j = 0; j < k*2 - 1; j += 2) {
dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
dp[i][j + 2] = Math.max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}
}
return dp[len - 1][k*2];
}
}