121. 买卖股票的最佳时机

题意

• 只能买卖股票各一次
• 求最大收益

解法 动态规划

要求最值，肯定要穷举。而穷举主要有两种方法：动态规划 和 回溯。

这道题显然可以使用动态规划的算法来解决，因为这里有一个很明显的子问题：前 $i$ 天的最大利润 $=$ 第 $i$ 天的价格 $-$ 前 $(i-1)$ 天的最小值。其中，求前 $i$ 天的最小值可以使用动态规划来求解。

求前 $i$ 天的最小值 ：

• 状态变量： tmp[i] 表示前 $i$ 天的最小值，其中，$0<=i<=n$
• 初始状态：tmp[0] = INT_MAX;
• 状态转移方程：tmp[i] = min(tmp[i - 1], prices[i - 1]);

注意：由于状态变量 tmp 需要赋一个初始值，所以 tmp 的有效下标为 $0-n$，其中 $1-n$ 对应 prices 的 $0-(n-1)$。

class Solution {
public:int minPrice(vector<int>& prices) {vector<int> tmp(prices.size() + 1, 0);tmp[0] = 1e9;for(int i = 1; i <= prices.size(); i++){tmp[i] = min(tmp[i - 1], prices[i - 1]);}return tmp[prices.size()];}
};

那么，最大收益也就可以解决了：

class Solution {
public:int maxProfit(vector<int>& prices) {vector<int> tmp(prices.size() + 1, 0);tmp[0] = 1e9;int ans = 0;for(int i = 1; i <= prices.size(); i++){tmp[i] = min(tmp[i - 1], prices[i - 1]);ans = max(ans, prices[i - 1] - tmp[i]);}return ans;}
};

但是，考虑到 tmp[i] 的状态转移只与 tmp[i - 1]有关，因此可以只用一个变量来代替 tmp[]：

class Solution {
public:int maxProfit(vector<int>& prices) {int tmp = 1e9;int ans = 0;for(int i = 1; i <= prices.size(); i++){tmp = min(tmp, prices[i - 1]);ans = max(ans, prices[i - 1] - tmp);}return ans;}
};

复杂度

时间复杂度：$O(n)$。
空间复杂度：$O(1)$。

---

122. 买卖股票的最佳时机 II

题意

• 每天最多只能持有一只股
• 可多次买卖
• 求最大收益

解法 动态规划

这道题与上一题的变化在于，状态变多了。对于每天来说，一共有两个状态：持有股票 或者 未持有股票，一共有三种操作可以进行状态转移：不操作、买入、卖出。

• 状态变量： dp[i][2]，dp[i][0] 表示第 $i$ 天未持有股票时获得的最大利润，dp[i][1]表示第 $i$ 天持有股票时获得的最大利润，其中，$0<=i<=n$，$0$ 对应初始化，$1-n$ 对应 $prices[0]-prices[n-1]$。
• 初始状态：dp[0][0] = 0, dp[0][1] = -prices[0];，其中，要想在第 $0$ 天就持有股票，那只能持有 $prices[0]$，并且此时利润为负。
• 状态转移方程：
  • 如果当天没有股票，可能是前一天也没有股票（不进行操作），或者前一天持有股票而当天卖出（卖出操作）；
  • 如果当天持有股票，可能是前一天就持有股票（不进行操作），或者前一天没有股票而当天买入（买入操作）；
  • 因此，状态转移方程如下：
    dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]);
dp[i][1] = max(dp[i - 1][0] - prices[i - 1], dp[i - 1][1]);

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(n + 1, vector<int>(2));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 - 1]);dp[i][1] = max(dp[i - 1][0] - prices[i - 1], dp[i - 1][1]);}return max(dp[n][0], dp[n][1]);}
};

复杂度

时间复杂度：$O(n)$。
空间复杂度：$O(n)$。

---

买卖股票的最佳时机 III

题意

• 最多只能进行两次买卖，且只有结束了一次买卖，才能开启下一次买卖
• 求最大利润

解法 动态规划

关于这道题，第一想法是暴力。因此一共只有两次买卖，所以将 prices[] 分成两段，对于两段分别进行最多一次买卖的最大利润的求取，然后将两次利润相加得到答案，这样就转换成了 121 题。

但是看了看数据范围，这样的做法，复杂度为$O(n^2)$，显然会超时。

代码如下：

class Solution {
public:int subMaxProfit(vector<int>& prices, int st, int end){int tmp = prices[st];int ans = 0;for(int i = st; i <= end; i++){tmp = min(tmp, prices[i]);ans = max(ans, prices[i] - tmp);}return ans;}int maxProfit(vector<int>& prices) {int pro1 = 0, pro2 = 0;int n = prices.size();int ans = 0;for(int i = 0; i < prices.size(); i++){pro1 = subMaxProfit(prices, 0, max(i, 0));pro2 = subMaxProfit(prices, min(i + 1, n - 1), n - 1);ans = max(ans, pro1 + pro2);}return ans;}
};

果然超时。

所以还是选择 列举状态，构建状态转移方程。

一共有 5 种状态：

• 未买卖过
• 买一次
• 买一次，卖一次
• 买一次，卖一次，买一次
• 买一次，卖一次，买一次，卖一次

然后构建状态转移方程。

• 状态变量： buy1，sell1，buy2，sell2，第一种状态可以单纯用 0 来表示（因为没有利润为 0 ）。
• 初始状态：buy1 = -prices[0]，sell1 = 0，buy2 = -prices[0]，sell2 = 0。其中，sell1 = 0 表示买入 prices[0]，再卖出 prices[0]；sell2 = 0 表示买入 prices[0]，再卖出 prices[0]，再买入 prices[0]，再卖出 prices[0]。
• 状态转移方程：
  sell2 = max(buy2 + p, sell2);
buy2 = max(sell1 - p, buy2);
sell1 = max(buy1 + p, sell1);
buy1 = max(buy1, -p);

ps. 这里为了防止每一轮中 先更新的变量 影响 后更新的变量 的更新，我特意调整了更新顺序，保证每一个变量更新时，等号右边的状态变量都是上一轮的值。（但是不调整顺序似乎也不影响 ac？）

class Solution {
public:int maxProfit(vector<int>& prices) {int buy1 = -prices[0], sell1 = 0, buy2 = -prices[0], sell2 = 0;for(auto p : prices){sell2 = max(buy2 + p, sell2);buy2 = max(sell1 - p, buy2);sell1 = max(buy1 + p, sell1);buy1 = max(buy1, -p);}return max(0, max(sell1, sell2));}
};

复杂度

时间复杂度：$O(n)$。
空间复杂度：$O(n)$。

---