解题框架
此系列的题目是买卖股票求得最大股票的问题。比如可以买卖1次、2次、k次、无数次，以及包含冷冻期、包含手续费等题目的变形，需要总结一个解题的套路。
参考labuladong大佬的解题框架比较好。参考链接：团灭leetcode股票问题
动态规划，dp[i][k][0 or 1]
0 <= i <= n-1, 1 <= k <= K
n 为天数，大 K 为最多交易数，0表示不持有股票，1表示持有股票
此问题共 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[2][3][0] 的含义：今天是第二天，我现在手上没有持有股票，至今最多进行 3 次交易。
我们想求的最终答案是 dp[n - 1][K][0]，即最后一天，最多允许 K 次交易，最多获得多少利润。可能问为什么不是 dp[n - 1][K][1]？因为 [1] 代表手上还持有股票，[0] 表示手上的股票已经卖出去了，很显然后者得到的利润一定大于前者。
状态转移方程：
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，所以今天我就持有股票了。
如果 buy，就要从利润中减去 prices[i]，如果 sell，就要给利润增加 prices[i]。今天的最大利润就是这两种可能选择中较大的那个。而且注意 k 的限制，我们在选择 buy 的时候，把 k 减小了 1，当然你也可以在 sell 的时候减 1，一样。
定义 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
解释：不允许交易的情况下，是不可能持有股票的，用负无穷表示这种不可能。
把上面的状态转移方程总结一下：
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])
leetcode121 买卖股票的最佳时机 (Easy)
题目来源：leetcode121 买卖股票的最佳时机
题目描述：
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
解题思路：
贪心，买入点维持在卖出前的最低点
class Solution {
public:
int maxProfit(vector<int>& prices) {
int str=0,end=0,max=0;
for(int i=0;i<prices.size();i++){
if(prices[i]<prices[str]) str=i;
if(prices[i]-prices[str]>max)
{
max=prices[i]-prices[str];
}
}
return max;
}
};
根据labuladong大佬框架解题,那么k是1，可以省略，简化框架。而且由于状态只和相邻有关，也可以只用一个变量保存，不用开二维空间。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n=prices.size();
int dp_i_0=0,dp_i_1=INT_MIN;
for(int i=0;i<n;i++){
dp_i_0=max(dp_i_0,dp_i_1+prices[i]);//第i天不持有股票，可能是因为i-1天不持有且第i天保持，或者i-1天持有且第i天卖掉（加上prices[i]）
dp_i_1=max(dp_i_1,-prices[i]);//第i天持有股票，可能是因为i-1天持有且第i天保持，或者i-1天不持有且第i天买入（减掉prices[i]）,由于只能买卖一次，则买入就是0-prices[i]
}
return dp_i_0;//返回最后一天不持有
}
};
leetcode 122 买卖股票的最佳时机II （Easy）
题目来源：leetcode 122 买卖股票的最佳时机II
题目描述：
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4
解题思路：
贪心，找谷底和峰顶
class Solution {
public:
int maxProfit(vector<int>& prices) {
int ans=0;
int i=0;
while(i<prices.size()-1){
while(i<prices.size()-1&&prices[i]>prices[i+1]) i++;
int str=i;
while(i<prices.size()-1&&prices[i]<prices[i+1]) i++;
int end=i;
if(end>str)
ans+=prices[end]-prices[str];
else i++;
}
return ans;
}
};
根据labuladong大佬框架解题,那么k是无穷大，k和k-1没什么区别，可以省略，简化框架。而且由于状态只和相邻有关，也可以只用一个变量保存，不用开二维空间。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n=prices.size();
int dp_i_0=0,dp_i_1=INT_MIN;
for(int i=0;i<n;i++){
int temp=dp_i_0;
dp_i_0=max(dp_i_0,dp_i_1+prices[i]);//第i天不持有股票，可能是因为i-1天不持有且第i天保持，或者i-1天持有且第i天卖掉（加上prices[i]）
dp_i_1=max(dp_i_1,temp-prices[i]);//第i天持有股票，可能是因为i-1天持有且第i天保持，或者i-1天不持有且第i天买入（减掉prices[i]）,需要包留上一次的dp_i_0，则买入就是它减掉prices[i]
}
return dp_i_0;//返回最后一天不持有
}
};
leetcode 309 最佳买卖股票时机含冷冻期(Medium)
题目来源：leetcode 309 最佳买卖股票时机含冷冻期
题目描述：
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:
输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
解题思路：
和leetcode122的区别是包含一个冷冻期一天，则第 i 天选择 buy 的时候，要从 i-2 的状态转移，而不是 i-1 。用dp_pre_0保存dp[i-2][0]
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n=prices.size();
int dp_i_0=0,dp_i_1=INT_MIN;
int dp_pre_0=0;//代表dp[i-2][0]
for(int i=0;i<n;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,dp_pre_0-prices[i]);
dp_pre_0=temp;
}
return dp_i_0;
}
};
leetcode 714 买卖股票的最佳时机含手续费(Medium)
题目来源：leetcode 714 买卖股票的最佳时机含手续费
题目描述：
给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例 1:
输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
输出: 8
解释: 能够达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
注意:
0 < prices.length <= 50000.
0 < prices[i] < 50000.
0 <= fee < 50000.
解题思路：
每次交易要支付手续费，只要把手续费从利润中减去即可。改写为：
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int n=prices.size();
int dp_i_0=0,dp_i_1=INT_MIN;
for(int i=0;i<n;i++){
int temp=dp_i_0;
//第i天不持有股票，可能是因为i-1天不持有且第i天保持，或者i-1天持有且第i天卖掉（加上prices[i]）
dp_i_0=max(dp_i_0,dp_i_1+prices[i]);
//第i天持有股票，可能是i-1天持有且第i天保持，或i-1天不持有且第i天买入,需要保留上一次的dp_i_0，把它减掉prices[i],交易减掉fee
dp_i_1=max(dp_i_1,temp-prices[i]-fee);
}
return dp_i_0;//返回最后一天不持有
}
};
leetcode 123 买卖股票的最佳时机 III(Hard)
题目来源：leetcode 123 买卖股票的最佳时机 III
题目描述：
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。
解题思路：
之前的状态转移k都省略了，因为0或者无穷大k无用。但是k=2时不能省略，因为k=2比较小，可以增加枚举、
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n=prices.size();
//天数是2，不能省略，也因为k=2较小，可以穷举
int dp_i1_0=0,dp_i1_1=INT_MIN;
int dp_i2_0=0,dp_i2_1=INT_MIN;
for(int i=0;i<n;i++){
//第二次交易
dp_i2_0=max(dp_i2_0,dp_i2_1+prices[i]);//前一次不持有保持，或者前一次持有，这次卖出
dp_i2_1=max(dp_i2_1,dp_i1_0-prices[i]);//前一次持有保持，或者前一次不持有，即第一次交易卖出后，这次买入为dp_i1_0-prices[i
//第一次交易
dp_i1_0=max(dp_i1_0,dp_i1_1+prices[i]);//前一次不持有保持，或者前一次持有，这次卖出
dp_i1_1=max(dp_i1_1,-prices[i]);//前一次持有保持，或者前一次不持有,这次买入，因为是第一次交易，直接是0-prices[i]
}
return dp_i2_0;//返回第二次交易不持有
}
};
leetcode 188 买卖股票的最佳时机 IV(Hard)
题目来源：leetcode 188 买卖股票的最佳时机 IV
题目描述：
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [2,4,1], k = 2
输出: 2
解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2:
输入: [3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
解题思路：
根据上一题k = 2,可以遍历枚举k的情况，但是会出现一个超内存的错误，原来是传入的 k 值会非常大，dp 数组太大了，可以考虑k的最大值。
一次交易由买入和卖出构成，至少需要两天。所以说有效的限制 k 应该不超过 n/2，如果超过，就没有约束作用了，相当于 k = +infinity。这种情况是之前解决过的。可以直接把之前的代码重用：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n=prices.size();
int dp_i_0=0,dp_i_1=INT_MIN;
for(int i=0;i<n;i++){
int temp=dp_i_0;
dp_i_0=max(dp_i_0,dp_i_1+prices[i]);//第i天不持有股票，可能是因为i-1天不持有且第i天保持，或者i-1天持有且第i天卖掉（加上prices[i]）
dp_i_1=max(dp_i_1,temp-prices[i]);//第i天持有股票，可能是因为i-1天持有且第i天保持，或者i-1天不持有且第i天买入（减掉prices[i]）,需要包留上一次的dp_i_0，则买入就是它减掉prices[i]
}
return dp_i_0;//返回最后一天不持有
}
int maxProfit(int k, vector<int>& prices) {
int n=prices.size();
if(k>n/2) return maxProfit(prices);
vector<vector<int>> dp(k+1,vector<int>(2,0));//k省略的时候，可以用一维，k不能省略用二维
for(int i=0;i<n;i++){
for(int j=k;j>=1;j--){
if(i==0){
dp[j][0]=0;
dp[j][1]=-prices[0];
}
else{
//状态转移雷同，只是枚举k
dp[j][0]=max(dp[j][0], dp[j][1] + prices[i]);
dp[j][1]=max(dp[j][1], dp[j-1][0] - prices[i]);
}
}
}
return dp[k][0];
}
};