dp[i][k][0 or 1]
0 <= i <= n-1, 1 <= k <= K
n 为天数，大 K 为最多交易数
此问题共 n × K × 2 种状态，全部穷举就能搞定。
for 0 <= i < n:
for 1 <= k <= K:
for s in {0, 1}:
dp[i][k][s] = max(buy, sell, rest)
// k = +infinity with fee
int maxProfit(vector<int>& prices, int fee) {
int len = prices.size();
int dp_i_0 = 0, dp_i_1 = INT_MIN; // i = -1
for(int i = 0; i < len; ++i){
int temp = dp_i_0;
dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]);
dp_i_1 = max(dp_i_1, temp - prices[i] - fee);
}
return dp_i_0;
}
第五题，k = 2
k = 2 和前面题目的情况稍微不同，因为上面的情况都和 k 的关系不太大。要么 k 是正无穷，状态转移和 k 没关系了；要么 k = 1，跟 k = 0 这个 base case 挨得近，最后也没有存在感。这道题 k = 2 和后面要讲的 k 是任意正整数的情况中，对 k 的处理就凸显出来了。这道题由于没有消掉 k 的影响，所以必须要对 k 进行穷举：
int maxProfit(vector<int>& prices) {
int len = prices.size();
int dp_0[3], dp_1[3];
// base case
for(int k = 0; k < 3; ++k){
dp_0[k] = 0, dp_1[k] = INT_MIN;
}
for(int i = 0; i < len; ++i){
for(int j = 1; j <= 2; ++j){
dp_0[j] = max(dp_0[j], dp_1[j] + prices[i]);
dp_1[j] = max(dp_1[j], dp_0[j - 1] - prices[i]);
}
}
// 穷举了 n × max_k × 2 个状态，正确。
return dp_0[2];
}
这里 k 取值范围比较小，所以可以不用 for 循环，直接把 k = 1 和 2 的情况全部列举出来也可以：
有了上一题 k = 2 的铺垫，这题应该和上一题的第一个解法没啥区别。但是出现了一个超内存的错误，原来是传入的 k 值会非常大，dp 数组太大了。现在想想，交易次数 k 最多有多大呢？一次交易由买入和卖出构成，至少需要两天。所以说有效的限制 k 应该不超过 n/2，如果超过，就没有约束作用了，相当于 k = +infinity。这种情况是之前解决过的。直接把之前的代码重用：
int maxProfit_infinity(std::vector<int>& prices){
int len = prices.size();
int dp_i_0 = 0, dp_i_1 = INT_MIN; // i = -1
for(int i = 0; i < len; ++i){
int temp = dp_i_0;
dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]);
dp_i_1 = max(dp_i_1, temp - prices[i]);
}
return dp_i_0;
}
int maxProfit(int k, vector<int>& prices) {
int len = prices.size();
if(k > len / 2)
return maxProfit_infinity(prices);
int dp_0[k + 1], dp_1[k + 1];
// base case
for(int t = 0; t <= k; ++t){
dp_0[t] = 0, dp_1[t] = INT_MIN;
}
for(int i = 0; i < len; ++i){
for(int j = 1; j <= k; ++j){
dp_0[j] = max(dp_0[j], dp_1[j] + prices[i]);
dp_1[j] = max(dp_1[j], dp_0[j - 1] - prices[i]);
}
}
return dp_0[k];
}
总结
动态规划关键就在于列举出所有可能的「状态」，然后想想怎么穷举更新这些「状态」。一般用一个多维 dp 数组储存这些状态，从 base case 开始向后推进，推进到最后的状态，就是我们想要的答案。具体到股票买卖问题，我们发现了三个状态，使用了一个三维数组，然后是确定每个状态下的选择，总共有三种选择，所以动态规划无非还是穷举（状态） + （选择）更新。
