买卖股票的最佳时机（动态规划方法总结）
总结一下，买卖股票系列的动态规划思想，贪心解法或者其他解法不做描述。
总结
121. 买卖股票的最佳时机 只有一次交易机会，每天有两种状态：持有股票和不持有股票；
122. 买卖股票的最佳时机 II 有多次交易机会，每天有两种状态：持有股票和不持有股票；
123. 买卖股票的最佳时机 III 至多两次交易机会，每天有 2*2=4 种状态：第一次持有股票；第一次不持有股票；第二次持有股票；第二次不持有股票；
188. 买卖股票的最佳时机 IV - 力扣（LeetCode）至多 k 次交易机会，与买卖股票 3 相比，每天有 2*k=2k 种状态：第一次持有股票；第一次不持有股票；第二次持有股票；第二次不持有股票... 第 k 次持有股票；第 k 次不持有股票。
买卖股票的最佳时机 Ⅰ
题目描述：给定一个数组
prices，它的第i个元素prices[i]表示一支给定股票第i天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回
0。
买卖股票系列的第一题，核心是只有一次交易机会。
dp 数组建立：
用两个 dp 数组来描述：
dp[i][0]第 i 天持有股票的最大剩余现金；dp[i][1]第 i 天不持有股票的最大剩余现金。
重要的是理解这里的“剩余现金”是什么含义：一开始，我们持有的现金为 0，买入一支股票i后，我们持有股票的剩余现金就是-prices[i]，而在第 i+k 天卖出股票后，我们不持有股票的剩余现金就是 prices[i+k] - prices[i]，也就是交易后的利润。
dp[0][0] = -prices[0]; 因为第 0 天要持有股票，只能购入第一支股票，剩余现金为 -prices[0]；
dp[0][1] = 0; 因为第 0 天只能买入股票，无法卖出股票，因此 dp[0][1] 初始化为 0。
递推公式：
dp[i][0] = max(dp[i-1][0], -prices[i]);第 i 天持有股票，有两种情况：
-
- 第一种，第
i天不买入股票，那么第i天持有股票的剩余现金就是第i-1天持有股票的剩余现金，即dp[i][0] = dp[i-1][0]; - 第二种，第
i天买入股票，那么第i天持有股票的剩余现金就是 0 减去第i天的股票价格，即dp[i][0] = -prices[i]; - 两者取最大值。
- 第一种，第
dp[i][1] = max(dp[i-1][1], prices[i] + dp[i-1][0]);同样有两种情况：
-
- 第一种，第
i天前已经不持有股票，那么第i天持有股票的剩余现金就是第i-1天持有股票的剩余现金，即dp[i][1] = dp[i-1][1]; - 第二种，第
i天当天才不持有股票，那么第i天持有股票的剩余现金就是第i天的股票价格 + 第i-1天持有股票的最大剩余现金，即dp[i][1] = prices[i] + dp[i-1][0]; - 两者取最大值。
- 第一种，第
完整代码：
class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();// dp[i][0] 第 i 天持有股票的最大剩余现金；// dp[i][1] 第 i 天不持有股票的最大剩余现金。vector<vector<int>> dp(n, vector<int>(2, 0));dp[0][0] = -prices[0];dp[0][1] = 0;for (int i = 1; i < n; ++i) {dp[i][0] = max(dp[i - 1][0], -prices[i]);dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);}return dp[n - 1][1];}
};买卖股票的最佳时机 Ⅱ
给你一个整数数组
prices，其中prices[i]表示某支股票第i天的价格。在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
买卖股票系列的第二题，和第一题的不同之处在于，可以多次买卖股票。
dp 数组建立：
用两个 dp 数组来描述：
dp[i][0]第 i 天持有股票的最大剩余现金；dp[i][1]第 i 天不持有股票的最大剩余现金。
dp[0][0] = -prices[0]; 因为第 0 天要持有股票，只能购入第一支股票，剩余现金为 -prices[0]；
dp[0][1] = 0; 因为第 0 天不管是不买股票，还是买了再卖出股票，都无法获得利润，因此 dp[0][1] 初始化为 0。
递推公式：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]);第 i 天持有股票，有两种情况：
-
- 第一种，第
i天不买入股票，那么第i天持有股票的剩余现金就是第i-1天持有股票的剩余现金，即dp[i][0] = dp[i-1][0]; - 第二种，第
i天买入股票，那么第i-1天就不能持有股票，因为在这道题目中连续购买两支股票没有意义，只会多花钱。第i天持有股票的剩余现金就是 第i-1天不持有股票的最大剩余现金减去第i天的股票价格，即dp[i][0] = dp[i-1][1] - prices[i]; - 两者取最大值。
- 第一种，第
dp[i][1] = max(dp[i-1][1], prices[i] + dp[i-1][0]);同样有两种情况：
-
- 第一种，第
i天前已经不持有股票，那么第i天持有股票的剩余现金就是第i-1天持有股票的剩余现金，即dp[i][1] = dp[i-1][1]; - 第二种，第
i天当天才不持有股票，同理，第 i-1 天必须是持有股票的，没有持有股票，怎么卖出股票呢？第i天持有股票的剩余现金就是第i天的股票价格 + 第i-1天持有股票的最大剩余现金，即dp[i][1] = prices[i] + dp[i-1][0]; - 两者取最大值。
- 第一种，第
完整代码：
class Solution {
public:int maxProfit(vector<int>& prices) {// 动态规划// dp[i][0] 表示第i天持有股票的最少消耗// dp[i][1] 表示第i天持有股票的最大利润vector<vector<int>> dp(prices.size(), vector<int>(2, 0));dp[0][0] = -prices[0];dp[0][1] = 0;for (int i = 1; i < prices.size(); ++i) {dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);}return dp[prices.size() - 1][1];}
};总结：
本题和121. 买卖股票的最佳时机的代码几乎一样，唯一的区别在：
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);因为本题的股票可以买卖多次！ 所以买入股票的时候，剩余现金可能包含之前买卖的所得利润：dp[i - 1][1]，所以 dp[i][0] 可能会等于 dp[i-1][1] - prices[i]。
想到到这一点，对这两道题理解的就比较深刻了。
买卖股票的最佳时机 Ⅲ
给定一个数组，它的第
i个元素是一支给定的股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
这题，要求我们在购入股票时，手上不能持有其他股票，且最多只能进行两笔交易。
前两道题，同一天只有两种状态：持有股票或者不持有股票
对于这道题，同一天可以有 4 种状态：
- 第一次持有股票
- 第一次不持有股票
- 第二次持有股票
- 第二次不持有股票
那么 dp[i][j] 就表示第 i 天的 j 状态下的最大剩余现金。
dp[0][0] = -prices[0];第 0 天第一次买入；
dp[0][1] = 0;
dp[0][2] = -prices[0];第 0 天第二次买入（第一次买入后卖出，再买入，有点蛇精病，但是为了做题，只能这么买了）
dp[0][3] = 0;
递推公式：
- 第 i 天第一次持有股票的最大剩余金额 = max(第 i-1 天第一次持有股票的最大剩余金额, -第 i 天股票价格)
- 第 i 天第一次不持有股票的最大剩余金额 = max(第 i-1 天第一次不持有股票的最大剩余金额, 第 i 天股票价格 + 第 i-1 天第一次持有股票的最大剩余金额)
- 第 i 天第二次持有股票的最大剩余金额 = max(第 i-1 天第二次持有股票的最大剩余金额, 第 i-1 天第一次不持有股票的最大剩余金额 - 第 i 天股票价格)
- 第 i 天第二次不持有股票的最大剩余金额 = max(第 i-1 天第二次不持有股票的最大剩余金额, 第 i-1 天第二次持有股票的最大剩余金额 + 第 i 天股票价格)
dp[i][0] = max(dp[i - 1][0], -prices[i]);
dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] - prices[i]);
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] + prices[i]);;完整代码：
注意，两次卖出的状态剩余现金最大一定是最后一次卖出。可以这么理解：如果第一次卖出已经是最大值了，那么我们可以在当天立刻买入再立刻卖出。所以dp[4][4]已经包含了dp[4][2]的情况。也就是说第二次卖出的剩余现金一定是最多的。
class Solution {
public:int maxProfit(vector<int>& prices) {// 动态规划// 1. 第一次持有股票// 2. 第一次不持有股票// 3. 第二次持有股票// 4. 第二次不持有股票vector<vector<int>> dp(prices.size(), vector<int>(4, 0));dp[0][0] = -prices[0];dp[0][1] = 0;dp[0][2] = -prices[0];dp[0][3] = 0;for (int i = 1; i < prices.size(); ++i) {dp[i][0] = max(dp[i - 1][0], -prices[i]);dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] - prices[i]);dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] + prices[i]);;}int result = max( dp[prices.size() - 1][1], dp[prices.size() - 1][3] );return result;}
};买卖股票的最佳时机 Ⅳ
给你一个整数数组
prices和一个整数k，其中prices[i]是某支给定的股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成
k笔交易。也就是说，你最多可以买k次，卖k次。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
与 123. 买卖股票的最佳时机 III 不同，这一次，我们最多可以完成 k 笔交易
那如果按照 3 的思路，我们可以用 dp[i][2 * k] 来描述第 i 天的 2k 种不同状态。
完整代码：
class Solution {
public:int maxProfit(int k, vector<int>& prices) {// 动态规划// 1. 第一次持有股票 dp[i][0]// 2. 第一次不持有股票 dp[i][1]// 3. 第二次持有股票 dp[i][2]// 4. 第二次不持有股票 dp[i][3]// ...// k次持有 dp[i][2 * k - 2]// k次不持有 dp[i][2 * k - 1]vector<vector<int>> dp(prices.size(), vector<int>(2 * k, 0));for (int i = 0; i < 2 * k; i+=2) {dp[0][i] = -prices[0];}for (int i = 1; i < prices.size(); ++i) {// 计算第一次的两个状态dp[i][0] = max(dp[i - 1][0], -prices[i]);dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);for (int j = 2; j <= k; ++j) {// 计算第2次到第k次的所有状态dp[i][2 * j - 2] = max(dp[i - 1][2 * j - 2], dp[i - 1][2 * j - 3] - prices[i]);dp[i][2 * j - 1] = max(dp[i - 1][2 * j - 1], dp[i - 1][2 * j - 2] + prices[i]);}}int result = dp[prices.size() - 1][2 * k - 1];return result;}
};