本文参考自：leetcode-cn题解、英文版。
建议直接看 LeetCode 题解，更加详细易懂，本文只是一个学习笔记。
LeetCode 上有一个系列的题目叫“买卖股票的最佳时机”，大致模板为：
给定一个数组，它的第
个元素是一支给定股票第 i 天的价格。如果你最多只允许完成
笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
具体的题目有：
121. 买卖股票的最佳时机（）
122. 买卖股票的最佳时机 II（）
123. 买卖股票的最佳时机 III（）
188. 买卖股票的最佳时机 IV（任意 ）
309. 最佳买卖股票时机含冷冻期（ with cooldown）
714. 买卖股票的最佳时机含手续费（ with fee）
解决这个系列题目的统一套路就是 DP table（状态表动态规划？），解题思路如下。
穷举框架
即穷举所有状态，具体到每一天，看看总共有多少种可能的状态，再找出每种状态对应的选择。我们要穷举所有的状态，穷举的目的是根据对应的选择更新状态。
for 状态1 in 状态1的所有取值：
for 状态2 in 状态2的所有取值：
for ...
dp[状态1][状态2][...] = 择优(选择1，选择2...)
这个问题的状态有三个：天数、允许交易的最大次数、是否持有。
选择则有三种：买入、卖出、无操作，但买入只能在卖出之后，卖出也只能在买入之后。
用一个三维数组表示全部的状态组合：
dp[i][k][s]
0 <= i <= n-1, 1 <= k <= K, s = 0 or 1
n 为天数，K 为最多交易数，s取值1/0表示是否持有
此问题共 n × K × 2 种状态，全部穷举就能搞定。
for 0 <= i < n:
for 1 <= k <= K:
for s in {0, 1}:
dp[i][k][s] = max(buy, sell, rest)
这个三维数组中的每个元素都可以用自然语言来描述，比如 dp[3][2][1] 的含义是：今天是第三天，现在手上持有着股票，至今最多进行 2 次交易。
状态转移框架
考虑每种状态下有哪些选择，以及每种选择该如何更新状态。只看持有状态，可以画个状态转移图：
持有状态转移图
根据状态转移图，写出状态转移方程：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
max( 选择 rest , 选择 sell )
解释：今天我没有持有股票，有两种可能：
要么是我昨天就没有持有，然后今天选择 rest，所以我今天还是没有持有；
要么是我昨天持有股票，但是今天我 sell 了，所以我今天没有持有股票了。
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
max( 选择 rest , 选择 buy )
解释：今天我持有着股票，有两种可能：
要么我昨天就持有着股票，然后今天选择 rest，所以我今天还持有着股票；
要么我昨天本没有持有，但今天我选择 buy，所以今天我就持有股票了。
定义 Base Case
即最简单的情况：
dp[-1][k][0] = 0
解释：因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0 。
dp[-1][k][1] = -infinity
解释：还没开始的时候，是不可能持有股票的，用负无穷表示这种不可能。
dp[i][0][0] = 0
解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0 。
dp[i][0][1] = -infinity
解释：不允许交易的情况下，是不可能持有股票的，用负无穷表示这种不可能。
DP table 关键点总结
base case：
dp[-1][k][0] = dp[i][0][0] = 0
dp[-1][k][1] = dp[i][0][1] = -infinity
状态转移方程：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
具体问题处理：
第一题，
int maxProfit_k_1(vector<int>& prices) {
int dp[2] = {0, -INT_MAX};
for(int i=0; i<prices.size(); i++){
dp[0] = max(dp[0], dp[1]+prices[i]);
dp[1] = max(dp[1], -prices[i]);
}
return dp[0];
}
第二题，
int maxProfit_k_inf(vector<int>& prices) {
int dp[2]={0, -INT_MAX}, temp;
for(int i=0; i<prices.size(); i++){
temp = dp[0];
dp[0] = max(dp[0], dp[1]+prices[i]);
dp[1] = max(dp[1], temp-prices[i]);
}
return dp[0];
}
第三题，
int maxProfit_k_2(vector<int>& prices) {
int dp[2][2]={0, -INT_MAX, 0, -INT_MAX};
for(int i=0; i<prices.size(); i++){
dp[1][0] = max(dp[1][0], dp[1][1]+prices[i]);
dp[1][1] = max(dp[1][1], dp[0][0]-prices[i]);
dp[0][0] = max(dp[0][0], dp[0][1]+prices[i]);
dp[0][1] = max(dp[0][1], -prices[i]);
}
return dp[1][0];
}
第四题，任意
int maxProfit_k_any(int k, vector<int>& prices) {
if(k<1) return 0;
if(k>prices.size()/2) return maxProfit_k_inf(prices);
vector<int> dp0, dp1;
dp0.resize(k, 0);
dp1.resize(k, -INT_MAX);
int temp;
for(int i=0; i<prices.size(); i++){
for(int j=0; j<k; j++){
temp = j>0? dp0[j-1]:0;
dp0[j] = max(dp0[j], dp1[j]+prices[i]);
dp1[j] = max(dp1[j], temp-prices[i]);
}
}
return dp0[k-1];
}
第五题， with cooldown
int maxProfit_cool(vector<int>& prices) {
int dp[2]={0, -INT_MAX}, pre=0, temp;
for(int i=0; i<prices.size(); i++){
temp = dp[0];
dp[0] = max(dp[0], dp[1]+prices[i]);
dp[1] = max(dp[1], pre-prices[i]);
pre = temp;
}
return dp[0];
}
第六题， with fee
int maxProfit_fee(vector<int>& prices, int fee) {
int dp[2]={0, -INT_MAX}, temp;
for(int i=0; i<prices.size(); i++){
temp = dp[0];
dp[0] = max(dp[0], dp[1]+prices[i]);
dp[1] = max(dp[1], temp-prices[i]-fee);
}
return dp[0];
}
