企业官网建设流程全解析

1. 动态规划解股票买卖问题：从入门到精通

股票买卖问题是算法学习中经典的动态规划应用场景。这类问题看似简单，却蕴含着丰富的状态转移思想。今天我们就来深入剖析三道LeetCode上的股票买卖问题（121、122、123题），掌握如何用动态规划解决不同约束条件下的最优交易策略。

1.1 问题背景与核心思路

股票买卖问题的核心是在给定的价格序列中，通过买卖操作获取最大利润。不同的问题变体会对交易次数、持股状态等做出限制。动态规划之所以适合这类问题，是因为：

1. 具有最优子结构：最终最大利润取决于子问题的解
2. 存在重叠子问题：不同天的状态会重复计算
3. 需要记录状态：持股与否会影响后续决策

我们将使用状态机的方法来建模，定义dp[i][j]表示第i天处于j状态时的最大利润。关键在于：

• 准确定义状态含义
• 正确写出状态转移方程
• 合理初始化边界条件

2. 单次交易问题（121题）

2.1 问题描述与建模

给定一个数组prices，其中prices[i]是某股票第i天的价格。你只能完成一次买卖（买入和卖出一支股票），求最大利润。

状态定义：

• dp[i][0]：第i天不持有股票时的最大利润
• dp[i][1]：第i天持有股票时的最大利润

状态转移：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1]) dp[i][1] = max(dp[i-1][1], -prices[i-1])

注意prices数组是0-based索引，而dp数组是1-based，所以prices[i-1]对应第i天的价格

2.2 关键实现细节

class Solution: def maxProfit(self, prices: List[int]) -> int: n = len(prices) dp = [[0]*2 for _ in range(n+1)] dp[0][1] = -float('inf') # 第0天持有股票不合法 for i in range(1, n+1): dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1]) dp[i][1] = max(dp[i-1][1], -prices[i-1]) return dp[n][0]

注意事项：

1. 初始化dp[0][1]为负无穷，表示不可能的状态
2. 只能买卖一次，所以买入时的利润是-prices[i-1]（没有之前的利润积累）
3. 最终结果是dp[n][0]，因为卖出股票后才能实现利润

2.3 复杂度分析

• 时间复杂度：O(n)，只需遍历一次价格序列
• 空间复杂度：O(n)，可以优化到O(1)只保存前一天的状态

3. 多次交易问题（122题）

3.1 问题变化与调整

现在允许进行多次交易（买入和卖出一支股票多次），但不能同时参与多笔交易（必须在再次购买前出售掉之前的股票）。

状态定义不变，但状态转移变化：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1]) dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i-1])

关键区别在于买入时的利润计算：dp[i-1][0] - prices[i-1]，这表示可以累积之前的利润。

3.2 实现代码

class Solution: def maxProfit(self, prices: List[int]) -> int: n = len(prices) dp = [[0]*2 for _ in range(n+1)] dp[0][1] = -float('inf') for i in range(1, n+1): dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1]) dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i-1]) return dp[n][0]

3.3 实战技巧

1. 这题也可以用贪心法，收集所有上升区间的利润
2. 动态规划的优势在于可以处理更复杂的约束条件
3. 空间优化版本：

hold, not_hold = -float('inf'), 0 for price in prices: hold = max(hold, not_hold - price) not_hold = max(not_hold, hold + price) return not_hold

4. 最多两次交易问题（123题）

4.1 状态扩展与建模

现在限制最多可以完成两笔交易。我们需要扩展状态来表示不同的交易阶段。

五种状态：

0. 无操作
1. 第一次买入
2. 第一次卖出
3. 第二次买入
4. 第二次卖出

状态转移：

dp[i][0] = dp[i-1][0] dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i-1]) dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i-1]) dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i-1]) dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i-1])

4.2 完整实现

class Solution: def maxProfit(self, prices: List[int]) -> int: n = len(prices) dp = [[0]*5 for _ in range(n+1)] # 初始化非法状态 for j in range(1, 5): dp[0][j] = -float('inf') for i in range(1, n+1): dp[i][0] = dp[i-1][0] dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i-1]) dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i-1]) dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i-1]) dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i-1]) return max(dp[n][0], dp[n][2], dp[n][4])

4.3 关键点解析

1. 状态1和3表示持有股票，状态2和4表示不持有
2. 每次买入都依赖前一次卖出的利润
3. 最终结果取max(dp[n][0], dp[n][2], dp[n][4])，因为可能在0次、1次或2次交易后获得最大利润

5. 常见问题与调试技巧

5.1 数组索引偏移问题

股票价格数组通常是0-based（第0天到第n-1天），而dp数组为了处理边界条件常用1-based（第0天到第n天）。常见的错误包括：

• 错误地使用prices[i]而不是prices[i-1]
• 忘记初始化dp[0][j]的边界条件

调试技巧：打印出完整的dp表格，检查每个状态的转移是否符合预期

5.2 状态转移错误

常见错误包括：

1. 混淆买入和卖出的状态转移方向
2. 在多次交易问题中忘记累积之前的利润
3. 在两次交易问题中错误地连接状态转移

检查方法：手动计算小例子（如3天的价格序列），验证dp值是否正确

5.3 空间优化实现

上述解法空间复杂度都是O(n)，实际上可以优化到O(1)：

def maxProfit(prices): # 121题空间优化 min_price = float('inf') max_profit = 0 for price in prices: min_price = min(min_price, price) max_profit = max(max_profit, price - min_price) return max_profit # 123题空间优化 buy1 = buy2 = -float('inf') sell1 = sell2 = 0 for price in prices: buy1 = max(buy1, -price) sell1 = max(sell1, buy1 + price) buy2 = max(buy2, sell1 - price) sell2 = max(sell2, buy2 + price) return max(sell1, sell2, 0)

6. 扩展与变种问题

掌握了这三道基础问题后，可以尝试以下变种：

1. 含冷冻期（卖出后需要等待一天才能买入）
2. 含交易手续费（每次卖出需要扣除手续费）
3. 最多k次交易（将两次交易推广到k次）

这些问题的解决思路都是类似的：定义足够的状态，正确写出状态转移方程，处理好边界条件。

在实际面试中，建议先从简单版本开始，逐步扩展到复杂情况。动态规划问题的解决关键在于：

1. 明确状态定义
2. 正确推导状态转移
3. 合理初始化
4. 确定最终解的位置

通过反复练习这些股票买卖问题，可以深入理解动态规划的状态设计和转移技巧，为解决更复杂的动态规划问题打下坚实基础。