My code:
public class Solution {
public int maxProfit(int k, int[] prices) {
if (k <= 0 || prices == null || prices.length == 0) {
return 0;
}
int len = prices.length;
if (k >= (len / 2)) {
int maxProfit = 0;
for (int i = 1; i < len; i++) {
if (prices[i] > prices[i - 1]) {
maxProfit += prices[i] - prices[i - 1];
}
}
return maxProfit;
}
int[][] dp = new int[k + 1][len];
for (int i = 1; i <= k; i++) {
int maxProfit = dp[i - 1][0] - prices[0];
for (int j = 1; j < len; j++) {
dp[i][j] = Math.max(dp[i][j - 1], maxProfit + prices[j]);
maxProfit = Math.max(maxProfit, dp[i - 1][j] - prices[j]);
}
}
return dp[k][len - 1];
}
}
reference:
https://discuss.leetcode.com/topic/26169/clean-java-dp-solution-with-comment/5
这道题目是看答案后做的。
dp[i][j] 表示，进行 i次交易， 从0-j 天范围内，可以取得的最大的收益。
那么，
dp[i][j] 可能有两种取值。
第一， prices[j] 在整个买卖策略中，被卖掉了
那么，一定是 [0, p] 完成了 i - 1次交易，然后买入prices[p],然后再在第 j 天 卖掉prices[j], 完成了 i 次交易。
p << [0, j - 1]
第二， prices[j] 在整个买卖策略中，并没有被卖掉。
此时最大值是， dp[i][j - 1]
于是：
dp[i][j] = Math.max(dp[i][j - 1], maxProfit + prices[j]);
maxProfit 不断地记录， dp[i - 1][p] - prices[p] 的最大值
然而这样并不能通过测试， TLE
问题在于，如果k很大很大，一百万，而天数就几百天，完全没必要用dp来解答，可以直接用 系列的第二题来解答。
于是加入一个判断，如果 k >= (n / 2), 则至少每两天都可以交易一次。那么就可以直接用简单地方法处理，不用DP。
时间复杂度： O(n * k)
空间复杂度： O(n * k)
下面说下我的解法。是一个三维DP
My code:
public class Solution {
public int maxProfit(int k, int[] prices) {
if (k <= 0 || prices == null || prices.length == 0) {
return 0;
}
int len = prices.length;
int[][][] dp = new int[len][len][k + 1];
initialize(prices, dp);
for (int m = 2; m <= k; m++) {
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
int max = dp[i][j][m - 1];
for (int n = j - 1; n >= i; n--) {
max = Math.max(max, dp[i][n][m - 1] + dp[n][j][1]);
}
dp[i][j][m] = max;
}
}
}
return dp[0][len - 1][k];
}
private void initialize(int[] prices, int[][][] dp) {
int len = dp.length;
for (int i = 0; i < len; i++) {
int min = prices[i];
int maxProfit = 0;
for (int j = i + 1; j < len; j++) {
if (prices[j] >= min) {
maxProfit = Math.max(maxProfit, prices[j] - min);
dp[i][j][1] = maxProfit;
}
else {
min = prices[j];
dp[i][j][1] = maxProfit;
}
}
}
}
}
时间复杂度： O(k * (n ^ 3))
空间复杂度： O(k * (n ^ 2))
dp[i][j][k] 表示 从 i 天 到 j 天， 经历 k 次交易所能获得的最大利润。
然后我想到了那道题目，
Palindrome Partitioning II
maxProfit = Math.max(maxProfit, dp[i][p][k - 1] + dp[p][j][1]);
最后写了出来。觉得复杂度还可以接受，没想到还是TLE
然后这道题目还可以有另外一种解法，但肯定TLE
也就是 recursion DP + divide and conquer + cache
只不过切分的时候，最多只能切分k次
Anyway, Good luck, Richardo! -- 08/21/2016
