别再死记硬背状态转移方程了！手把手带你‘画’出股票买卖两次的最优解（信息学奥赛1302题）

可视化拆解动态规划：从股票买卖两次到通用交易策略

看着屏幕上跳动的股票K线图，你有没有想过——如果给你两次买卖机会，如何抓住最佳时机？这个问题看似简单，却难倒了不少算法学习者。传统的动态规划教学往往直接抛出状态转移方程，让人一头雾水。今天，我们将用全新的可视化方法，带你一步步"画"出最优解。

1. 问题本质与直观理解

股票买卖两次的问题，核心在于找到两个不重叠的交易区间，使得两次买卖的利润总和最大。想象你面前有一张股价走势图，你需要用两支不同颜色的荧光笔，标出两个买入和卖出的区间。

为什么这个问题适合用动态规划解决？因为它具有两个关键特征：

1. 最优子结构：全局最优解包含局部最优解。两次交易的最优解，必然由两个单次交易的最优解组合而成。
2. 重叠子问题：计算后面区间的最大值时，会重复用到前面区间的计算结果。

传统解法通常会直接给出四个状态定义：第一次买入后、第一次卖出后、第二次买入后、第二次卖出后的最大利润。但这种抽象定义往往让初学者困惑——这些状态是怎么来的？为什么这样定义？

2. 从可视化到状态定义

让我们换种思路，从图形角度理解状态定义。假设我们有以下股价序列：

[3, 5, 2, 6, 1, 4]

2.1 绘制利润潜力图

首先，我们计算两个辅助数组：

1. 前向最大利润（dpe）：记录到第i天为止，单次交易能获得的最大利润
2. 后向最大利润（dpb）：记录从第i天开始，单次交易能获得的最大利润

计算过程可以用下表展示：

2.2 寻找最佳分割点

现在，我们需要找到一个分割点i，使得dpe[i] + dpb[i+1]最大。这相当于在前i天做一次最佳交易，在后n-i天再做一次最佳交易。

def maxProfit(prices): n = len(prices) if n < 2: return 0 # 计算前向最大利润dpe dpe = [0] * n min_price = prices[0] for i in range(1, n): min_price = min(min_price, prices[i]) dpe[i] = max(dpe[i-1], prices[i] - min_price) # 计算后向最大利润dpb dpb = [0] * n max_price = prices[-1] for i in range(n-2, -1, -1): max_price = max(max_price, prices[i]) dpb[i] = max(dpb[i+1], max_price - prices[i]) # 寻找最佳分割点 max_profit = 0 for i in range(n-1): max_profit = max(max_profit, dpe[i] + dpb[i+1]) return max_profit

3. 通用化思考：k次交易的情况

理解了两次交易的情况后，我们可以进一步思考：如果允许最多k次交易呢？这时状态定义需要扩展：

1. 状态定义：dp[i][j]表示第i天结束时，已经完成j次交易的最大利润
2. 状态转移：
   • 不操作：dp[i][j] = dp[i-1][j]
   • 完成第j次卖出：dp[i][j] = max(dp[i-1][j], dp[m][j-1] + prices[i] - prices[m+1])，其中m < i

这种通用解法的时间复杂度是O(kn²)，可以通过优化降低到O(kn)。关键思路是避免重复计算最小值：

def maxProfitKTransactions(prices, k): if not prices: return 0 n = len(prices) if k >= n // 2: # 相当于可以无限次交易 return sum(max(prices[i+1]-prices[i], 0) for i in range(n-1)) dp = [[0] * n for _ in range(k+1)] for j in range(1, k+1): min_cost = prices[0] for i in range(1, n): min_cost = min(min_cost, prices[i] - dp[j-1][i-1]) dp[j][i] = max(dp[j][i-1], prices[i] - min_cost) return dp[k][n-1]

4. 实战技巧与常见陷阱

在实际应用中，股票买卖问题有几种常见变体和需要注意的陷阱：

4.1 边界条件处理

• 空输入或单日价格的情况
• 所有价格递减，无法获利的情况
• k值极大（超过n/2）时退化为无限次交易

4.2 空间优化技巧

观察状态转移方程，可以发现dp数组通常只依赖前一行或前一列，因此可以将二维数组优化为一维：

def maxProfitKTransactionsOptimized(prices, k): if not prices: return 0 n = len(prices) if k >= n // 2: return sum(max(prices[i+1]-prices[i], 0) for i in range(n-1)) dp_prev = [0] * n for _ in range(k): dp_curr = [0] * n min_cost = prices[0] for i in range(1, n): min_cost = min(min_cost, prices[i] - dp_prev[i-1]) dp_curr[i] = max(dp_curr[i-1], prices[i] - min_cost) dp_prev = dp_curr return dp_prev[-1]

4.3 实际应用中的调整

真实股票交易还需要考虑：

• 交易手续费（每次卖出时扣除）
• 冷冻期（卖出后需要等待一天才能买入）
• 持仓限制（最多持有一股）

例如，带冷冻期的问题状态定义需要调整：

def maxProfitWithCooldown(prices): if not prices: return 0 n = len(prices) hold = -prices[0] # 持有股票的最大利润 cash = 0 # 不持有股票，可以买入 cooldown = 0 # 不持有股票，处于冷冻期 for i in range(1, n): new_hold = max(hold, cash - prices[i]) new_cash = max(cash, cooldown) new_cooldown = hold + prices[i] hold, cash, cooldown = new_hold, new_cash, new_cooldown return max(cash, cooldown)

5. 从算法到直觉：培养交易思维

经过这样的可视化训练，你会逐渐培养出对动态规划问题的直觉。当面对新的交易策略问题时，可以按照以下步骤思考：

1. 图形化价格序列：先画出价格走势图，直观感受高低点
2. 识别关键操作：明确买入、卖出、持有等基本操作
3. 定义状态：根据操作定义账户状态（持有现金、持有股票等）
4. 建立状态转移：思考每种操作如何改变账户状态
5. 优化空间：观察状态依赖关系，减少存储需求

这种思维方式不仅适用于股票交易问题，还可以迁移到其他动态规划场景，如背包问题、路径规划等。关键在于将抽象的状态转移具象化为可视的操作步骤。