买卖股票最佳时机
I
II 不限制交易次数
prices = [7,1,5,3,6,4]
启发思路：最后一天发生了什么？
从第0天到第5天结束时的利润 = 从第0天到第4天结束时的利润 + 第5天的利润
（第5天的利润：0/-4/4）
关键词：天数 / 是否持有股票
分解子问题：到第i天结束，持有/未持有股票的最大利润
下一子问题：到第i-1天结束时，持有/未持有股票的最大利润
状态转移图
定义dfs(i, 0)表示到第i天结束，未持有股票的最大利润
定义dfs(i, 1)表示到第i天结束，持有股票的最大利润
由于第i-1天的结束就是第i天的开始，dfs(i-1, .)也表示到第i天开始时的最大利润
状态转移图中：
卖出：dfs(i, 0) = dfs(i - 1, 1) + prices[i]
买入：dfs(i, 1) = dfs(i - 1, 0) - prices[i]
未持有状态下无动作：dfs(i, 0) = dfs(i - 1, 0)
持有状态下无动作：dfs(i, 1) = dfs(i - 1, 1)
汇总公式：
dfs(i, 0) = max(dfs(i - 1, 0), dfs(i - 1, 1) + prices[i])
dfs(i, 1) = max(dfs(i - 1, 1), dfs(i - 1, 0) - prices[i])
递归边界：
dfs(-1, 0) = 0 // 第0天开始未持有股票，利润为0
dfs(-1, 1) = INT_MIN // 第0天开始不可能持有股票
递归入口：
max(dfs(n - 1, 0), dfs(n - 1, 1)) = dfs(n - 1, 0)
思路：
class Solution {
public:// 优化方向：改为cacheint dfs(int i, bool hold, const std::vector<int> &prices) {// 边界if (i < 0) {return hold ? INT_MIN : 0;}if (hold) {return max(dfs(i - 1, true, prices), dfs(i - 1, false, prices) - prices[i]);}return max(dfs(i - 1, false, prices), dfs(i - 1, true, prices) + prices[i]);}int maxProfit(std::vector<int> prices) {int n = prices.size();return dfs(n - 1, false, prices);}
};
实际代码
class Solution {
public:int maxProfit(std::vector<int> prices) {int n = prices.size();vector<std::pair<int, int>> res(n + 1);res[0].second = INT_MIN;for (auto i = 0; i < n; ++i) {res[i + 1].first = max(res[i].first, res[i].second + prices[i]);res[i + 1].second = max(res[i].second, res[i].first - prices[i]);}return res[n].first;}
};// 演进
class Solution {
public:int maxProfit(std::vector<int> prices) {int n = prices.size();int f0{};int f1{INT_MIN};for (auto i = 0; i < n; ++i) {int new_f0 = max(f0, f1 + prices[i]);f1 = max(f1, f0 - prices[i]);f0 = new_f0;}return f0;}
};
III 冷冻期 309
class Solution {
public:int maxProfit(std::vector<int> prices) {int n = prices.size();int f0{-prices.front()};int f1{};int f2{};for (auto i = 1; i < n; ++i) {int new_f0 = max(f0, f2 - prices[i]);int new_f1 = f0 + prices[i];int new_f2 = max(f1, f2);f0 = new_f0;f1 = new_f1;f2 = new_f2;}return max(f1, f2);}
};