博文中会简要介绍Leetcode P0188题目分析及解题思路。
“Best Time to Buy and Sell Stock IV”是一道原型题，其要求计算最多买卖k次所能获得的最大收益。p0123这篇博文中的动态规划通用解法其实已经解决了这道原型题，下面这篇博文同样会给出基于动态规划的通用思路。
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).
首先，我们可以到得到最优子结构，如下，
dp[i][j]表示前i天里最多交易j次的最大收益
如此一来，当我们得到dp[n][k]时，就能得到在这个n天的区间内能够得到的最大收益。得到最优子结构后，我们就能够比较容易地得到递推表达式，如下，
令dp[i][j]表示前i天里最多交易j次的最大收益
dp[0][0] = 0
dp[i][0] = 0
dp[0][i] = 0
显然无论是那种情况，如果允许的交易次数为零或者股票预测区间的长度为零，都会导致实际的收益为零，
dp[i][j] = max(dp[i][j-1], prices[j]-prices[m]+dp[m][j-1]), 1 <= m <= i-1
这里其实表示，前i天如果最多交易j次的话，最大收益只有两种可能，一种是不交易第j次，那么此时收益就相当于在前i天里交易j-1次；第二种是在交易第j次，并且是第m天买入，第i天卖出，那么此时收益就等于第i天股价和第m天股价的差值再加上前m天内的最大收益。
这里有个小优化。如果我们按照上述递推表达式来做，那么动态规划维度是三维的，也就是说时间复杂度会上升到O(n^3)。但是如果我们观察此式，会发现，
max(dp[i][j-1], prices[j]-prices[m]+dp[m][j-1]) = max(dp[i][j-1], prices[j]+max(dp[m][j-1]-prices[m]))
也就是说，我们如果知道了下式的值，
max(dp[m][j-1]-prices[m]))
就可以直接参与计算。而这个式子的值在遍历到第m天的时候就可以计算出来，也就是说我们对i进行遍历的时候，不需要每次再用m从1遍历到i-1，而是可以通过维护一个变量去记录第m天的该式的值即可
除了上述动态规划解法以外，需要注意的是，如果k非常大，申请数组空间的时候容易触发“超出限定空间”的错误。这里需要进行一些简单的剪枝，若k大于了数组长度的一半，也就是说我们可以在任何一个极小值点买入，在下一个极大值点卖出，此时我们只需要扫一遍数组即可以得到最终结果。
以下是Java的题解代码实现。
class Solution {
public int maxProfit(int k, int[] prices) {
if (prices.length <= 1)
return 0;
int days = prices.length;
// Pruning
if (k >= days/2) {
int profit = 0;
for (int day=0; day<days-1; ++day) {
if (prices[day] < prices[day+1])
profit += prices[day+1]-prices[day];
}
return profit;
}
int[][] dp = new int[days+1][k+1];
// DP
for (int j2=1; j2<=k; ++j2) {
int localMax = dp[0][j2-1]-prices[0];
for (int i1=1; i1<=days; ++i1) {
dp[i1][j2] = Math.max(dp[i1-1][j2], prices[i1-1]+localMax);
localMax = Math.max(localMax, dp[i1][j2-1]-prices[i1-1]);
}
}
return dp[days][k];
}
}
以下是C++的题解代码实现。
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int days = prices.size();
if (days <= 1)
return 0;
if (k >= days/2) {
int profit = 0;
for (int day=0; day<days-1; ++day) {
if (prices[day] < prices[day+1])
profit += prices[day+1]-prices[day];
}
return profit;
}
vector<vector<int>> dp(days+1, vector<int>(k+1, 0));
// DP;
for (int j2=1; j2<=k; ++j2) {
int local_max = dp[0][j2-1]-prices[0];
for (int i1=1; i1<=days; ++i1) {
dp[i1][j2] = max(dp[i1-1][j2], prices[i1-1]+local_max);
local_max = max(dp[i1][j2-1]-prices[i1-1], local_max);
}
}
return dp[days][k];
}
};