Say you have an array for which the i-th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most k transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Example 1:
Input: [2,4,1], k = 2 Output: 2 Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4),
profit = 4-2 = 2.Example 2:
Input: [3,2,6,5,0,3], k = 2 Output: 7 Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6),
profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3),
profit = 3-0 = 3.
买卖股票的最佳时机IV。这是股票系列的第四题了，题目基本设定还是跟前三个版本一样，但是这道题问的是如果你最多可以交易K次，请问你的最大收益是多少。
经过前面的题，这道题依然需要用动态规划做。我参考了一个讲的很好的题解。这里我们第一次接触到三维的DP。这里dp[i][j][K]的定义是：到下标为 i 的天数为止（从 0 开始），到下标为 j 的交易次数（从 0 开始），以状态为K的情况下，最大收益是多少。这里的状态K用0或1分别表示不持有和持有股票，也只有这两种状态。
这个题有几个边界条件需要排除。当K == 0的时候，也就是没有交易次数的时候，最大收益就是0，因为没有买也没有卖。当K >= 数组长度的一半的时候，这道题就转化为了版本二的贪心算法。因为K的次数包含了买和卖，换言之一次买卖就得占用两次交易次数，所以当K大于数组长度的一半的时候，用贪心算法算出最大收益即可。
接下来是处理几种一般情况，
当i == 0的时候，也就是第0天的时候，如果当前是持有状态，那么初始值就是-prices[0]；如果当前是不持有状态，初始值是0
当 i 不为0但是持有股票[i][j][1]的话，分两种情况
如果交易次数j == 0，也就是不允许交易的话，当前位置持股的DP值 dp[i][j][1] 是前一天持股的DP值 dp[i - 1][j][1] 和今天买了股票 -prices[i] 之间的较大值
如果交易次数 j 不为0，那么当前位置持股的DP值 dp[i][j][1] 是前一天持股的DP值dp[i - 1][j][1] 和前一天不持股但是买了股票 dp[i - 1][j - 1][0] - prices[i] 之间的较大值
对于其他情形，也就是在某一天不持有股票的话dp[i][j][0]，DP值就是 前一天不持有股票dp[i - 1][j][0] 和 前一天持有股票但是今天卖掉了 dp[i][j - 1][1] + prices[i] 之间的较大值
因为最后返回的时候，利益更大的一定是在不持有的这个状态上，所以返回的是dp[len - 1][k - 1][0]
时间O(n^2)
空间O(n^3) - 三维矩阵
Java实现
1 class Solution {
2 public int maxProfit(int k, int[] prices) {
3 int len = prices.length;
4 // 特判
5 if (k == 0 || len < 2) {
6 return 0;
7 }
8 if (k >= len / 2) {
9 return greedy(prices, len);
10 }
11
12 // dp[i][j][K]：到下标为 i 的天数为止（从 0 开始），到下标为 j 的交易次数（从 0 开始）
13 // 状态为 K 的最大利润，K = 0 表示不持股，K = 1 表示持股
14 int[][][] dp = new int[len][k][2];
15 // 初始化：把持股的部分都设置为一个较大的负值
16 for (int i = 0; i < len; i++) {
17 for (int j = 0; j < k; j++) {
18 dp[i][j][1] = -9999;
19 }
20 }
21
22 // 编写正确代码的方法：对两个"基本状态转移方程"当 i - 1 和 j - 1 分别越界的时候，做特殊判断，赋值为 0 即可
23 for (int i = 0; i < len; i++) {
24 for (int j = 0; j < k; j++) {
25 if (i == 0) {
26 dp[i][j][1] = -prices[0];
27 dp[i][j][0] = 0;
28 } else {
29 if (j == 0) {
30 dp[i][j][1] = Math.max(dp[i - 1][j][1], -prices[i]);
31 } else {
32 // 基本状态转移方程 1
33 dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
34 }
35 // 基本状态转移方程 2
36 dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
37 }
38 }
39 }
40 // 说明：i、j 状态都是前缀性质的，只需返回最后一个状态
41 return dp[len - 1][k - 1][0];
42 }
43
44 private int greedy(int[] prices, int len) {
45 // 转换为股票系列的第 2 题，使用贪心算法完成，思路是只要有利润，就交易
46 int res = 0;
47 for (int i = 1; i < len; i++) {
48 if (prices[i - 1] < prices[i]) {
49 res += prices[i] - prices[i - 1];
50 }
51 }
52 return res;
53 }
54 }