「动态规划」线性DP：股票问题合集 / LeetCode 121|122|123|188 （C++）
目录
概述
Question1
思路
算法过程
Code
复杂度
Question2
思路
解题过程
Code
复杂度
Question3
思路
解题过程
Code
复杂度
Question4
思路
解题过程
Code
复杂度
总结
概述
我们已经了解过了线性DP：
「动态规划」线性DP：最长上升子序列（LIS）|编辑距离 / LeetCode 300|72（C++）
更进一步，我们来解决非常经典的线性DP问题系列：买卖股票。
Question1
LeetCode 121：
给定一个数组
prices，它的第i个元素prices[i]表示一支给定股票第i天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回
0。示例 1：
输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
思路
我们来找到规模更小的子问题。
对于本题来说，什么是规模更小的子问题？
先来考虑有几个状态：现在第几天，手里有没有股票，是否交易过。
定义dp[i][j][k]，表示：
第i天，j为0代表未交易，j为1代表完成交易过（即发生了买入与卖出），k为0代表手中无股票，k为1表示手中有股票，此时所能拥有的最大利润。
初始条件：dp[0][0][0] = 0, dp[0][0][1] = -prices[0];
算法过程
每个子问题都要被求解，前提是比它小的问题被求解了，而不论大小规模，这些问题的求解过程是一样的。
对于dp[i][0][0]与dp[i][1][1]没有意义，因为dp[i][0][0]恒为0；而题意只能进行一次交易，故dp[i][1][1]无意义。
对于已完成交易且手中无票，这个状态来自前一天的相同状态或前一天为未完成交易且手中有票。
对于未完成交易且手中有票，这个状态来自前一天的相同状态或前一天为未完成交易且手中无票。
所以应该是这样的：
dp[i][1][0] = max(dp[i - 1][1][0], dp[i - 1][0][1] + prices[i]);
dp[i][0][1] = max(dp[i - 1][0][1], dp[i - 1][0][0] - prices[i]);Code
class Solution {
public:int maxProfit(vector<int>& prices) {const int n = prices.size();vector<array<array<int, 2>, 2>> dp(n);dp[0][0][1] = -prices[0];for (int i = 1; i < n; i++){dp[i][1][0] = max(dp[i - 1][1][0], dp[i - 1][0][1] + prices[i]);dp[i][0][1] = max(dp[i - 1][0][1], dp[i - 1][0][0] - prices[i]);}return max(0, dp[n - 1][1][0]);}
};复杂度
时间复杂度: O(n) //需求解n个状态，每次求解通过二分进行。
空间复杂度: O(n) //预留dp数组空间
Question2
LeetCode 122：
给你一个整数数组
prices，其中prices[i]表示某支股票第i天的价格。在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1：
输入：prices = [7,1,5,3,6,4] 输出：7 解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。 最大总利润为 4 + 3 = 7 。
思路
这次更简单了。
去掉第二维，只保留时间和有无票两个状态dp[i][j]。
初始条件：dp[0][0] = 0, dp[0][1] = -prices[0];
解题过程
去掉第二维后事情更简单了。
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]);Code
class Solution {
public:int maxProfit(vector<int>& prices) {const int n = prices.size();vector<array<int, 2>> dp(n);dp[0][0] = 0, dp[0][1] = -prices[0];for (int i = 1; i < n; 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[n - 1][0];}
};复杂度
时间复杂度: O(n)
空间复杂度: O(n)
Question3
LeetCode 123：
给定一个数组，它的第
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 。
思路
两次交易依然是一次交易的思路。
定义dp[i][j][k]，表示：
第i天，j为0代表未交易，j代表已完成交易的次数，k为0代表手中无股票，k为1表示手中有股票，此时所能拥有的最大利润。
初始条件：
dp[0][0][1] = -prices[0];
dp[0][1] = {INT_MIN / 2, INT_MIN / 2};
dp[0][2] = {INT_MIN / 2, INT_MIN / 2};
考虑用INT_MIN表示非法状态，INT_MIN / 2来避免后续减法越界。
解题过程
我们用循环来处理2次交易。
单独计算j = 0，然后循环计算j = {1, 2}。
for (int i = 1; i < n; i++) {dp[i][0][1] = max(dp[i - 1][0][1], dp[i - 1][0][0] - prices[i]);for (int j : {1, 2}) {dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j - 1][1] + prices[i]);dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j][0] - prices[i]);}
}*注意*:这里使用了对初始化列表{1, 2}的范围for循环，语法糖，不得不品鉴。
Code
class Solution {
public:int maxProfit(vector<int>& prices) {const int n = prices.size();vector<array<array<int, 2>, 3>> dp(n);dp[0][0][1] = -prices[0];dp[0][1] = {INT_MIN / 2, INT_MIN / 2};dp[0][2] = {INT_MIN / 2, INT_MIN / 2};for (int i = 1; i < n; i++) {dp[i][0][1] = max(dp[i - 1][0][1], dp[i - 1][0][0] - prices[i]);for (int j : {1, 2}) {dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j - 1][1] + prices[i]);dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j][0] - prices[i]);}}int ans = INT_MIN;for (int j = 0; j < 3; j++)ans = max(ans, dp[n - 1][j][0]);return ans;}
};复杂度
时间复杂度: O(n)
空间复杂度: O(n)
Question4
LeetCode 188：
给你一个整数数组
prices和一个整数k，其中prices[i]是某支给定的股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成
k笔交易。也就是说，你最多可以买k次，卖k次。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1：
输入：k = 2, prices = [2,4,1] 输出：2 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
思路
将之前的代码拓展到k天。
定义dp[i][j][k]，表示：
第i天，j为0代表未交易，j代表已完成交易的次数，k为0代表手中无股票，k为1表示手中有股票，此时所能拥有的最大利润。
初始条件：
dp[0][0][0] = 0;
dp[0][0][1] = -prices[0];
dp[0][p > 0][q] = {INT_MIN / 2, INT_MIN / 2};
解题过程
我们用循环来处理k次交易。
单独计算j = 0，然后循环计算j。
for (int i = 1; i < n; i++) {dp[i][0][1] = max(dp[i - 1][0][1], dp[i - 1][0][0] - prices[i]);for (int j = 1; j <= k; j++) {dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j - 1][1] + prices[i]);dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j][0] - prices[i]);}
}Code
class Solution {
public:int maxProfit(int k, vector<int>& prices) {const int n = prices.size();vector<vector<array<int, 2>>> dp(n, vector<array<int, 2>>(k + 1, {INT_MIN / 2, INT_MIN / 2}));dp[0][0][0] = 0;dp[0][0][1] = -prices[0];for (int i = 1; i < n; i++) {dp[i][0][1] = max(dp[i - 1][0][1], dp[i - 1][0][0] - prices[i]);for (int j = 1; j<= k; j++) {dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j - 1][1] + prices[i]);dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j][0] - prices[i]);}}int ans = INT_MIN;for (int j = 0; j <= k; j++)ans = max(ans, dp[n - 1][j][0]);return ans;}
};复杂度
时间复杂度: O(n * k)
空间复杂度: O(n * k)
总结
线性dp的状态定义是尤为重要的，希望你有所体会。