买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
思路
买卖股票除了确定买卖日期之外，还需要确定当天股票的状态
股票状态有两种：持有和不持有
为什么不用"买入"和"卖出"来作为状态？
因为买入和卖出仅能代表两种状态，即买入和卖出
什么意思呢？就比如第i天你卖出了股票，好那第i+1天如果你不卖股票，那应该是什么状态？
如果还用“卖出”状态来表示，那么就意味着第i+1天仍然要卖出股票，但实际上我们想表示的是这样一种状态：“第i天卖出股票后，如果第i+1天不卖，那么第i天卖掉股票后的状态应该持续到第i+1天”
因此，使用"买入"和"卖出"来作为状态会漏掉一些状态，还得单独为那些情况设定对应的状态进行表示
五步走
1、确定dp数组含义
根据思路，我们需要的dp数组应该是二维的
dp[i][0]:代表第i天持有股票所得到的最大收益
dp[i][1]:代表第i天不持有股票所得到的最大收益
这里在解释一下"持有"和"不持有"
持有指的是我现在手头上有某只股票，但不一定是今天买的，有可能是之前某一天买的，然后该状态延续到了现在
不持有指的是手头上已经没有股票了，但不一定是今天卖的，有可能是之前卖掉了，然后该状态持续到了现在（因为本题的股票只能买卖一次，因此该状态会持续到最后一天）
2、确定递推公式
因为dp的定义是"持有"和"不持有"两种，因此这两种情况需要分开讨论
（1）持有股票
第i天持有股票（dp[i][0]）的状态可以通过两种情况推导得到：
- 第i天买了股票
- 第i - 1天之前买了股票
因为本题只能买卖一次股票，因此不管在哪天买入股票，都是第一次买入
因为我们的初始现金是0，所以在买入股票之后，此时的最大收益是 -price[i]，即dp[i][0] = -price[i]。因为买股票花钱了嘛，此时的状态变为持有股票
然后如果是第i天不卖入股票，但状态仍是持有股票的话，那么此时的状态是dp[i][0] = dp[i - 1][0]
综上，取两者最大的情况，那么持有股票时的递推公式为：dp[i][0] = max(dp[i - 1][0], -price[i])
（2）不持有股票
第i天持有股票（dp[i][1]）的状态可以通过两种情况推导得到：
- 第i天卖了股票
- 第i - 1天之前卖了股票
如果是在第i天卖了股票，那么此时除了状态需要转换为持有股票（并且是i - 1天持有，因为第i天卖掉了就不持有了），还需要加上第i天的股价price[i]作为收益，即dp[i][1] = price[i] + dp[i - 1][0]
如果是在第i - 1天之前卖了股票，那么此时状态还是不持有股票，即dp[i][1] = dp[i - 1][1]
综上，取两者最大的情况，那么不持有股票时的递推公式为：dp[i][1] = max(dp[i - 1][1], price[i] + dp[i - 1][0])
3、初始化dp数组
从两种情况下的递推公式来看，dp[0][1]和dp[0][0]是递推的基础，因此需要对其进行初始化
结合dp数组的定义，dp[0][1]是第0天不持有股票所得到的最大收益，那没有股票肯定是0啊，而且我们初始资金也是0，即dp[0][1]=0
而dp[0][0]则是第0天持有股票所得到的最大收益，因为是第0天，所以不会存在前一天的情况
因此持有的股票一定是第0天购买的，所以dp[0][0] = -price[i]
4、确定遍历顺序
dp[i][1]由dp[0][1]推导而来，因此需要顺序遍历
代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
if(len == 0) return 0;
//定义dp数组
vector<vector<int>> dp(len, vector<int>(2));
//初始化
dp[0][0] = -prices[0];
dp[0][1] = 0;
//遍历dp数组
for(int i = 1; i < len ;++i){
dp[i][0] = max(dp[i - 1][0], -prices[i]);//持有股票
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);//不持有股票
}
return dp[len - 1][1];
}
};
为什么返回值是
dp[len - 1][1]而不是max(dp[len][0], dp[len][1])？
如果认为max(dp[len][0], dp[len][1])是返回值的话，存在两个错误
（1）len - 1才是最后一天，不是len
（2）题目要求最大利润，但没有要求具体在哪个状态达成
在这个题目中，只需要求最终的最大利润，而不需要知道具体是在哪个状态（持有股票或不持有股票）达到了最大利润，因此直接返回dp[len - 1][1]即可。这是因为题目中规定，最后一天必须卖出所有持有的股票，而不是可以选择继续持有。
在遍历到最后一天后，dp[len-1][0]表示最后一天持有股票的最大收益，而dp[len-1][1]则表示最后一天不持有股票的最大收益。
我们只需要考虑最后一天的状态，也就是持有股票和不持有股票的两种情况，因为最后一天无法再进行任何交易了，只有卖出股票才能获得收益。因此，我们只需要返回最后一天不持有股票的最大收益 dp[len-1][1] 即可。
买卖股票的最佳时机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
思路
基本的思路和 I 一致
唯一不同的地方，就是推导dp[i][0]和dp[i][0]的时候，第i天买入股票的情况。
这里再推导一下所有的情况吧
（1）持有股票dp[i][0]
如果是第i天买入的，那么要用没有持有该股票时有的钱减去股票的售价，即dp[i][0] = dp[i - 1][1] - prices[i]
如果是第i-1天买入的，就还是和上一题一样，状态延续到第i天即可，即dp[i][0] = dp[i - 1][0]
综上，dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);//持有
（2）不持有股票dp[i][1]
如果是第i天卖掉的，那就要用持有该股票时有的钱加上卖股票得的钱，即dp[i][1] = dp[i - 1][0] + prices[i]
如果是第i-1天卖掉的，延续第i天的状态即可，即dp[i][1] = dp[i - 1][1]
综上，dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);//不持有
代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();//获取prices数组长度（天数）
if(len == 0 ) return 0;
vector<vector<int>> dp(len, vector<int>(2));//创建dp数组
dp[0][0] = -prices[0];//初始化
dp[0][1] = 0;
for(int i = 1; i < len; ++i){
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);//持有
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);//不持有
}
return dp[len - 1][1];//最后一天要求把股票卖掉，返回不持有股票的最大金钱数
}
};
买卖股票的最佳时机III
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1: 输入：prices = [3,3,5,0,0,3,1,4] 输出：6 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3。
示例 2： 输入：prices = [1,2,3,4,5] 输出：4 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3： 输入：prices = [7,6,4,3,1] 输出：0 解释：在这个情况下, 没有交易完成, 所以最大利润为0。
示例 4： 输入：prices = [1] 输出：0
提示：
- 1 <= prices.length <= 10^5
- 0 <= prices[i] <= 10^5
思路
与之前的两题最大的不同是，之前一天只可以进行一次交易（买卖），总的交易次数也只有1次
而现在一天可以交易两次，总的次数也是两次
至多买卖两次，意味着可以买卖一次，可以买卖两次，也可以不买卖。
五步走
1、确定dp数组含义
回忆一下，之前只能买卖一次时，我们有两种情况，即：第i天持有或不持有股票
现在因为可以进行两次买卖，所以第i天可能有的所有情况（假设在第i天就进行两次交易，就会有四种情况）有四种：
- 0、没有操作--
dp[i][0] - 1、第i天第一次持有股票--
dp[i][1] - 2、第i天第一次不持有股票--
dp[i][2] - 3、第i天第二次持有股票--
dp[i][3] - 4、第i天第二次不持有股票--
dp[i][4]
即dp[i][j]中，i表示第i天，j表示状态
dp[i][j]表示第i天状态j所剩最大现金
2、确定递推公式
dp[i][0]先不用管，后面要初始化
达到dp[i][1]状态（第一次持有股票），有两个具体操作：
- 操作一：第i天买入股票了，那么
dp[i][1] = dp[i-1][0] - prices[i]（用前一天状态下还剩的钱减去第i天买入股票的价格） - 操作二：第i天没有操作，而是沿用前一天买入的状态，即：
dp[i][1] = dp[i - 1][1]
取最大结果：dp[i][1] = max(dp[i- 1][0] - prices[i], dp[i - 1][1]);
dp[i][2]（第一次不持有股票）同理：
- 操作一：第i天卖出股票了，那么
dp[i][2] = dp[i - 1][1] + prices[i]（ ） - 操作二：第i天没有操作，沿用前一天卖出股票的状态，即：
dp[i][2] = dp[i - 1][2]
取最大结果：dp[i][2] = max(dp[i - 2][1] - prices[i], dp[i - 1][2]);
按上面的形式可以把剩余的情况在不同操作下的状态推导出来：
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
3、初始化dp数组
（1）如果第0天没有操作，那就是0，即dp[0][0] = 0
（2）如果第0天第一次操作
- 在第0天第一次买入，初始现金为0，那么现在要扣除买股票的钱，即
dp[0][1] = -prices[0] - 在第0天第一次卖出，即
dp[0][2] = 0
如果第0天的第一次操作就是卖出，那此时都没有东西，卖什么呢？
这种情况可以理解为在同一天先买入了，然后又在当天卖出
买卖都是相同的价格，相当于钱花出去了又原路返回，因此
dp[0][2] = 0由此我们可以发现，第一次卖出的操作是依赖第一次买入操作的
（3）如果第0天第二次操作
- 在第0天第二次买入。
dp[0][3] = -prices[0]
所谓的“第二次买入”，意味着我之前已经买入过一次了，也就是说第二次买入依赖于第一次卖出的状态
又因为题目规定买完必须先卖掉才能再买，所以“第二次买入”时，已经经过了第一次买入和卖出
因此在第0天第二次买入时，手头上的钱仍然是0，那么买入之后的状态自然就是 -prices[0]
- 在第0天第二次卖出。
dp[0][4] = 0
与在第0天第一次卖出同理
4、确定遍历顺序
i由i-1推出，因此仍是从小到大遍历，即顺序遍历
代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() == 0) return 0;
//创建dp数组
vector<vector<int>> dp(prices.size(), vector<int>(5, 0));
//初始化,根据分析进行初始化
dp[0][1] = -prices[0];
dp[0][3] = -prices[0];
//遍历dp数组
for(int i = 1; i < prices.size(); ++i){
dp[i][0] = dp[i - 1][0];//不进行操作
//第i天第一次进行操作
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);//不操作|买入股票，用前一天状态下还剩的钱减去第i天买入股票的价格
dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);//不操作|卖出股票，用前一天状态下还剩的钱加上第i天卖掉股票的收益
//第i天第二次进行操作
dp[i][3] = max(dp[i - 1][3],dp[i - 1][2] - prices[i]);//不操作|买入股票
dp[i][4] = max(dp[i - 1][4],dp[i - 1][3] + prices[i]);//不操作|卖出股票
}
return dp[prices.size() - 1][4];
}
};
买卖股票的最佳时机IV
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1： 输入：k = 2, prices = [2,4,1] 输出：2 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2。
示例 2： 输入：k = 2, prices = [3,2,6,5,0,3] 输出：7 解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4。随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
提示：
- 0 <= k <= 100
- 0 <= prices.length <= 1000
- 0 <= prices[i] <= 1000
思路
本题与上题的不同点在于买卖次数，现在我们可以任意买卖k次了
从上题来看，买卖两次已经需要列出4个状态了（不算不操作状态），因此在k次交易的条件下，罗列处所有状态是可能的
需要使用循环去控制
五步走
1、dp数组的含义
与上一题一样
二维数组 dp[i][j] ：dp[i][j]表示第i天状态j所剩最大现金
j的状态可以表示为：
- 0 表示不操作
- 1 第一次买入
- 2 第一次卖出
- 3 第二次买入
- 4 第二次卖出
- .....
除了0以外，上述状态的规律可以总结为：偶数卖出，奇数买入
因为买卖次数变成k次，每多一次买卖会新增两种状态，所以dp数组的大小要设置为2k + 1
vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));
2、确定递推公式
正如上面的分析，k次买卖的话是不可能都列出来所有状态的，因此需要进行抽象，抽象出一个通用的递推公式
先来看看上一题中，两次买卖时的递推公式：
dp[i][0] = dp[i - 1][0];//不进行操作
//第i天第一次进行操作
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);//不操作|买入股票，用前一天状态下还剩的钱减去第i天买入股票的价格
dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);//不操作|卖出股票，用前一天状态下还剩的钱加上第i天卖掉股票的收益
//第i天第二次进行操作
dp[i][3] = max(dp[i - 1][3],dp[i - 1][2] - prices[i]);//不操作|买入股票
dp[i][4] = max(dp[i - 1][4],dp[i - 1][3] + prices[i]);//不操作|卖出股票
这里可以发现，二维dp数组中，第二个维度我们是写成具体数字的，用来表示买入和卖出状态
可以使用一个变量j来代替具体的数字，j + 1表示买入；j + 2表示卖出
使用for循环控制j，j从0开始循环，每次自增2
for(int j = 0; i < 2 * k; j += 2){
dp[i][j] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);//不操作|奇数买入,用前一天状态下还剩的钱减去第i天买入股票的价格
dp[i][j] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);//不操作|偶数卖出,用前一天状态下还剩的钱加上第i天卖掉股票的收益
}
类比j为奇数是买，偶数是卖的状态。
为什么j是小于2 * k，而不是别的值，比如2 * k - 1 ？
遇到边界不确定的情况时，就代入具体值来判断是否合理
这里假设一共至多可以买卖2次
如果j < 2 * k ,那么 j < 4
以上面 两次买卖时的递推公式 为例来看
当循环开始，
j = 0，所以 j + 1 指向
dp[i][1]， j + 2 指向dp[i][2]，一切正常j = 2，所以 j + 1 指向
dp[i][3]， j + 2 指向dp[i][4]，一切正常j = 3，所以 j + 1 指向
dp[i][3]， j + 2 指向dp[i][4]，一切正常j = 4，循环结束，所有状态被完整覆盖，边界正确
3、初始化dp数组
基本上与买卖III的思路一致
（1）如果第0天没有操作，那就是0，即dp[0][0] = 0
（2）如果第0天第一次操作
- 在第0天第一次买入，初始现金为0，那么现在要扣除买股票的钱，即
dp[0][1] = -prices[0] - 在第0天第一次卖出，即
dp[0][2] = 0
（3）如果第0天第二次操作
- 在第0天第二次买入。
dp[0][3] = -prices[0] - 在第0天第二次卖出。
dp[0][4] = 0
（关于推导的细节与注释详见买卖III）
我们还是从上面初始化中总结规律进行抽象
即：j为奇数时候，要初始化为-prices[0]；j为偶数时候，要初始化为0；
使用for循环进行初始化
for(int j = 1; j < 2 * k; j += 2){
dp[0][j] = -prices[0];//0在创建dp数组的时候就初始化了
}
为什么j是小于2 * k，而不是别的值，比如2 * k - 1 ？
还是代入来看, 这里假设至多可以买卖2次，那么 j < 4
当j = 1时，奇数初始化为-prices[0]
然后自增2，j = 3，奇数初始化为-prices[0]
再自增就超过4，结束循环，过程没有问题
4、确定遍历顺序
i由i-1推出，因此仍是从小到大遍历，即顺序遍历
代码
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if(prices.size() == 0) return 0;
//创建dp数组
vector<vector<int>> dp(prices.size() + 1, vector<int>(2 * k + 1, 0));
//初始化dp数组
for(int j = 1; j < 2 * k; j += 2){
dp[0][j] = -prices[0];//0在创建dp数组的时候就初始化了，所以不用在此处初始化
}
//遍历dp数组
for(int i = 1; i < prices.size(); ++i){
for(int j = 0; j < 2 * k; j += 2){
//不操作|奇数买入,用前一天状态下还剩的钱减去第i天买入股票的价格
dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
//不操作|偶数卖出,用前一天状态下还剩的钱加上第i天卖掉股票的收益
dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}
}
return dp[prices.size() - 1][2 * k];//返回最后一天卖掉股票后的总金额
}
};