企业官网建设流程全解析

买股票这件事，大家平时听到的大多是K线、MACD、均线这些技术分析，但如果你去面试技术岗位，会发现"股票买卖"常常以另一种面目出现：给你一个价格数组，问你最多交易几次能赚到最大利润。这个场景几乎成了算法面试里动态规划的必考题，很多人在上面栽过跟头。今天就用动态规划的思路，把这类题目从头到尾拆一遍，把状态怎么设计、转移方程怎么推、代码怎么写、空间怎么优化，一次性讲透。

我在带模拟项目X的算法集训时，A同学第一次遇到这套题，按着贪心思路写了个"看见涨就卖"的版本，遇到无手续费时还能对，一旦加上冷静期和手续费就全盘崩掉。这类题真正的门槛不在题面，而在建模。先别急着看代码，我们先把思路上的坑一个个填平。

1. 为什么股票买卖题总在考动态规划

1.1 核心场景和真正的考察点

这类题目的原始描述通常是这样：给定一个整数数组 prices，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格，你最多可以完成 k 笔交易，求你能获得的最大利润。有的变体会附加条件，比如卖出后第二天不能再买入（冷静期）、每次交易要付手续费等等。

题面看起来像是在考金融知识，实际上是考你两个能力：第一，能不能把一个随时间变化、带状态约束的决策过程抽象成数学模型；第二，能不能用计算机高效地求解这个模型。

为什么动态规划在这里几乎是唯一的标准解？因为它天然适合处理"多阶段决策"问题。你每天面对的选择只有几个——买入、卖出、持有、观望，但一连串选择叠加起来，结果呈指数级增长。动态规划的核心工作，是把"某一时刻的状态"和"做出某类选择后的收益"归纳成一张表，让每一步都从表里查历史最优值，而不是重新枚举所有可能性。

1.2 贪心思路为什么会把人带偏

不少人第一反应是用贪心：只要明天的价格比今天高，今天就买、明天就卖，跑一个循环累加差值。这种做法对于"可以无限次交易且没有手续费"的简单版本确实是对的，因为同一天可以买又可以卖时，每次价差都正向累加即可。

但问题很快出现。如果你限制了总交易次数，比如最多交易 2 次，贪心就不知道怎么分配这两次交易的位置了。它只会看到局部的价差，无法判断"少赚一段、把交易次数省给后面更大的波动"这种全局取舍。再叠加冷净期约束时，贪心在"今天卖不卖"和"明天还能不能买"之间会陷入短视，结果经常比最优解差一大截。

注意，这里不是说贪心毫无用处，而是想说明：一旦决策依赖之前若干天的交易状态，并且存在跨天的约束关系，就需要一个能"记住历史状态"的算法框架，动态规划正好干这个事。

1.3 动态规划解题的通用三段式

面对这类题，我个人习惯固定走三步，这也是我给模拟项目X学员反复强调的流程。

第一步，定义状态，想清楚"dp 数组的每个维度表示什么"。对股票问题来说，天数、剩余交易次数、当前是否持仓，这三个维度基本涵盖了所有题目变体。

第二步，推导转移方程，想清楚"今天这个状态从哪来"。通常只有两条路：今天什么都没做，或者今天做了买入/卖出。把这两种来源都写成表达式，取最大或最小即可。

第三步，初始化与遍历顺序，想清楚"表从哪里开始填、每一行依赖哪一行"。股票问题里，dp[i] 几乎总是依赖 dp[i-1]，因此从第 0 天开始逐步递推就是最自然的顺序。

这套流程看起来很基础，但真正执行起来，大多数人会卡在第一步，也就是状态定义上。下面重点展开。

2. 状态设计：破题的核心钥匙

2.1 用三维数组表达完整决策空间

在各类股票买卖问题中，最高频使用的状态定义是这样：

dp[i][k][0] # 第 i 天结束时，已经进行了 k 笔交易，当前不持有股票，能获得的最大利润 dp[i][k][1] # 第 i 天结束时，已经进行了 k 笔交易，当前持有股票，能获得的最大利润

这里有个约定要先说清楚：把"买入"作为交易次数增加的标志，也就是说，完成一笔交易 = 一次买入 + 一次卖出，买入时 k 加 1，卖出时 k 不变。这样约定的好处是，买入动作发生在持有状态转变时，状态更新时只需在买入分支中对 k 做加法。

为什么用三维数组而不用二维？因为 k 这个维度承载了"最多交易几次"的硬约束。去掉 k，就退化成无限次交易模型；把 k 固定为 1 或 2，就又回到有限次交易的简单变体。把 k 留作变量，一套代码就能打完六种常见变体，这是三维状态的最大价值。

2.2 状态转移方程的推导逻辑

从第 i-1 天到第 i 天，不持有股票 dp[i][k][0] 只能来自两种可能：前一天也不持有，今天继续观望，利润不变；或者前一天持有，今天卖出，利润增加今天的价格。写成公式是这样：

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

持有股票 dp[i][k][1] 同样只有两种来源：前一天就持有，今天继续持有；或者前一天不持有，今天买入，利润减少今天的价格，同时 k 减 1（因为买入算新开启一笔交易）：

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

注意卖出分支里用的是 dp[i-1][k][1]，因为卖出不改变已完成交易次数；买入分支里用的是 dp[i-1][k-1][0]，因为它开启的是第 k 笔交易。

这两个方程是整个股票买卖问题家族的骨架，后面出现的所有变体基本都是对它做局部修改，比如把买入分支的 k-1 去掉，或者加手续费、冷静期。

2.3 初始化和边界条件的处理

初始化是新手翻车重灾区。先说第 0 天，也就是 i = 0 时：dp[0][k][0] 表示第一天开始前不持股且完成了 k 笔交易，利润自然是 0；dp[0][k][1] 表示第一天就持有股票，利润应该是 -prices[0]。这里要理解一个细节：第 0 天持有股票的唯一办法就是当天买入，所以无论前面交易次数是几，持有的利润都是负的当前价格。

再说 k = 0 的情况。k=0 与"不允许交易"等价，所以 dp[i][0][0] 恒为 0，dp[i][0][1] 在逻辑上不存在，可以设为一个极小的负数，比如-float('inf')，保证它在状态转移中永远不会被选中。

用代码写初始化，常见风格如下：

n = len(prices) if n == 0: return 0 max_k = 2 # 这里以最多 2 次交易为例 dp = [[[0] * 2 for _ in range(max_k + 1)] for _ in range(n)] for k in range(max_k + 1): dp[0][k][0] = 0 dp[0][k][1] = -prices[0]

边界条件齐了之后，剩下的事情就是按 i 从 1 到 n-1 循环，逐层填表。整个过程相当机械，但正因为机械，出错的概率低，适合作为面试时的兜底方案。

3. 六大变种的统一解法框架

3.1 只能交易一次：k=1 的状态压缩

先说最简单的版本：最多只能完成一笔交易。用三维状态直接套，max_k = 1 就行了，但我更推荐大家在理解三维模型的前提下，再用二维滚动数组来写，因为面试时经常要求现场写这类代码，简短清晰的版本更有优势。

def max_profit_one(prices): n = len(prices) if n < 2: return 0 dp_i_0 = 0 dp_i_1 = -prices[0] for i in range(1, n): dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]) dp_i_1 = max(dp_i_1, -prices[i]) return dp_i_0

为什么买入分支里直接写-prices[i]而不是dp[i-1][0][0] - prices[i]？因为 dp[i-1][0][0] 恒等于 0，表示之前没有完成过任何交易，手里利润为 0，买入后变成负数价格。这样代码就从三维降成了两个变量，空间复杂度 O(1)，时间复杂度 O(n)。

如果直接套三维通用框架，也是完全正确的，只是代码更长、占用空间更多。把通用框架写熟，再把这种特殊版本作为"推导结果"记忆，两边都不耽误。

3.2 无限次交易与手续费版本

去掉交易次数限制，k 维度就可以从状态里删除，只留下两个变量：

def max_profit_infinite(prices, fee=0): n = len(prices) if n < 2: return 0 dp_i_0 = 0 dp_i_1 = -prices[0] for i in range(1, n): # 卖出时扣手续费 new_dp_i_0 = max(dp_i_0, dp_i_1 + prices[i] - fee) new_dp_i_1 = max(dp_i_1, dp_i_0 - prices[i]) dp_i_0, dp_i_1 = new_dp_i_0, new_dp_i_1 return dp_i_0

这里唯一需要注意的问题是更新顺序。在 Python 中，如果直接写：

dp_i_0 = max(dp_i_0, dp_i_1 + prices[i] - fee) dp_i_1 = max(dp_i_1, dp_i_0 - prices[i])

第二行里的 dp_i_0 已经被第一行更新成了今天的值，再用于今天的买入计算就出错，相当于"今天既卖了又买了，还用了卖完后的钱再买"。正确做法是用两个新的临时变量，或者同时计算后再赋值。我在某次代码评审里看到过不下三个同学踩这个顺序坑，这里特别拿出来强调一次。

手续费的处理方式有讲究：可以在买入时扣，可以在卖出时扣，两种写法结果一样，但习惯上我推荐在卖出时扣，因为更贴近真实交易场景，也方便后续加冷静期时统一理解。

3.3 含冷静期的特殊约束处理

冷静期的约束是：卖出股票后，第二天不能再买入，至少要等一天。这给状态转移带来了额外分支。新的状态需要在"持有"和"不持有"之间再加一维，表示"今天是否处于冷静状态"。

常见做法是用三个状态变量：

def max_profit_cooldown(prices): n = len(prices) if n < 2: return 0 # 不持股且不在冷静期 dp_i_0 = 0 # 持股 dp_i_1 = -prices[0] # 不持股但处于冷静期（即今天刚卖出） dp_i_2 = 0 for i in range(1, n): new_dp_i_0 = max(dp_i_0, dp_i_2) # 昨天不持股或昨天冷静，今天可买入 new_dp_i_1 = max(dp_i_1, dp_i_0 - prices[i]) # 昨天持股，或昨天不持股今天买入 new_dp_i_2 = dp_i_1 + prices[i] # 今天卖出，进入冷静期 dp_i_0, dp_i_1, dp_i_2 = new_dp_i_0, new_dp_i_1, new_dp_i_2 return max(dp_i_0, dp_i_2)

这个版本里，dp_i_2 只能由"今天卖出"产生，来源唯一，所以不需要 max。dp_i_0 表示既能自由买又能自由卖的状态，它来自前一天不持股或不处于冷静期。三个状态变量的更新同样是同批计算后统一赋值，防止互相污染。

冷静期版本的难点不在方程本身，而在于理解"为什么要多一个变量"。答案很简单：昨天卖出会让今天处于禁买状态，如果你只用两个状态，就无法区分"昨天没持股是因为一直没买"还是"昨天刚卖完不能买"。多出的这个维度，就是用来保存这个"禁买标记"的。

3.4 最多两次和最多 K 次交易

最多两次交易是三维通用框架最常见的应用场景。直接用前面 2.1 的框架，max_k = 2 即可。我在模拟项目X里让学员手写这个版本时，发现最大的问题不是转移方程写错，而是第三维的索引总是搞混，比如在 dp[i][k][1] 的买入分支里用了 k 而不是 k-1。建议写完后手动代入一个例子验证。

如果题目升级为最多 K 次交易，思路完全不变，只是循环里多套一层 k 的循环。这种情况下，空间优化会比"两个变量"版本复杂一些，但可以用"每一天循环 k 时只保留前一天的一维数组"的方式压缩。

def max_profit_k(prices, K): n = len(prices) if n < 2 or K <= 0: return 0 if K > n // 2: # 超过 n//2 次交易时，退化为无限次交易模型，避免数组过大 return max_profit_infinite(prices) dp = [[0, -prices[0]] for _ in range(K + 1)] for i in range(1, n): for k in range(1, K + 1): pre = dp[k][0] dp[k][0] = max(dp[k][0], dp[k][1] + prices[i]) dp[k][1] = max(dp[k][1], pre - prices[i]) return dp[K][0]

注意这里有个 K 超过 n//2 的退化处理。因为一次完整的交易至少需要连续两天（买入和卖出），n 天最多能完成 n//2 次交易。一旦 K 超过这个上限，约束实际上没有意义，直接套无限次交易模型更快，还能避免不必要的大数组分配。K 较大的时候，这步优化不是锦上添花，而是防止内存超限的关键。

4. 空间优化与代码落地

4.1 为什么三维数组可以压缩成若干个变量

完整的三维数组占用的空间是 O(n*K)，当 K 很小比如 2 时，K≈常数，问题不大；但 K 可能到 100、1000，数组大小就会变成 O(n*K)，有超内存风险。我们观察转移方程，会发现 dp[i][...] 的所有更新都只依赖 dp[i-1][...]，第 i 天不用回头去看第 i-2 天是什么情况。这说明历史信息在用完的一瞬间就可以丢弃。

这就是滚动数组的直观理由。用两个变量承载"当前不持股"和"当前持股"的利润值，再配合一层 k 循环，可以把空间压到 O(K)，甚至在某些版本里压到 O(1)。

我实际操作中的体会是：写滚动数组版本前，先把三维版本完整写一遍并跑通，再逐行对照压缩。直接一步到位写压缩版，很容易在"今天的值"和"昨天的值"之间打架。

4.2 完整可运行的通用框架代码

下面给一个可以直接用的完整实现，max_k 作为参数传入，同时支持冷静期和手续费作为可选开关。这个版本不是最优到极致的写法，但结构清晰，适合作为模板。

def max_profit_all(prices, max_k, fee=0, cooldown=False): n = len(prices) if n < 2 or max_k <= 0: return 0 # K 过大时退化为无限次交易 if max_k > n // 2: return max_profit_infinite(prices, fee) # dp[k][0]: 最多 k 笔交易，当前不持股 # dp[k][1]: 最多 k 笔交易，当前持股 dp = [[0, -prices[0]] for _ in range(max_k + 1)] for i in range(1, n): for k in range(1, max_k + 1): pre0 = dp[k][0] pre1 = dp[k][1] if cooldown: # 简化处理：不持股但刚卖出，不能立刻买入。 # 这里用 dp[k][0] 的旧值代表不持股可买入状态， # 避免卖出后的当天立即买入。 dp[k][0] = max(pre0, pre1 + prices[i] - fee) dp[k][1] = max(pre1, dp[k - 1][0] - prices[i]) else: new0 = max(pre0, pre1 + prices[i] - fee) new1 = max(pre1, dp[k - 1][0] - prices[i]) dp[k][0], dp[k][1] = new0, new1 return dp[max_k][0]

注意 cooldown 的简化处理在实际使用时不够严谨，它无法完全替代 3.3 里的三状态版本，因为真正的冷静期需要区分"昨天卖出"还是"昨天之前就不持股"。这段代码的目的主要是示范：怎么在同一个框架里组织多个逻辑开关。

严谨的冷静期实现请看 3.3 的版本，那个版本更贴合题目原始约束。

4.3 参数计算和复杂度评估方法

时间复杂度上，滚动数组版本是 O(n*K)，其中 n 是天数，K 是最大交易次数；空间复杂度是 O(K)。如果 K 是常数，比如题目固定 K=2，那时间就是 O(n)，空间 O(1)。

如果某个变体把 K 设成无限，也就是不限制交易次数，那时间退化成 O(n)，空间 O(1)，对应 3.2 里的两变量版本。

评估复杂度时还有一个隐含条件：prices 数组的长度。如果 n 很大，比如 10 万，但 K 只有 2，三维数组版本需要分配 10万*3*2 个整数，内存大约几 MB 到几十 MB，可以用；但 K 变成 1 万时就不行了，必须走滚动数组或者退化处理。这也是为什么我总说，"先求正确，再求空间优化"，但在 K 很大的题目里，空间优化不是可选项而是必选项。

5. 常见问题与排查技巧实录

5.1 状态更新顺序如何影响结果

这是我在教学和 code review 中遇到频率最高的一类问题。看下面这段典型的错解：

# 错误示范 dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]) dp_i_1 = max(dp_i_1, dp_i_0 - prices[i])

逻辑错误在于第二行的 dp_i_0 已经不是昨天的值了，而是今天卖出后的值。这样计算 dp_i_1 时，相当于允许"今天卖出后再买入同一天股票"，而真实规则一般不允许同日买卖，更关键的是，这可能导致重复利用同一天的价格差，放大利润。

排查方法很简单：把 prices 设为 [1, 2, 3]，手算一遍正确结果应为 2。错误版本可能得出 3，一对比就露馅。凡是遇到结果偏大、难以解释的情况，优先检查是否踩了这个顺序坑。

5.2 数组索引越界和 K 值异常

K 值处理的坑也有代表性。比如 max_k = 0，此时很多代码会直接数组越界，因为 dp[0] 虽然存在，但循环里for k in range(1, max_k + 1)一次都不会执行，最终返回 dp[0][0] = 0，逻辑正确但依赖 dp 数组的初始化。建议在函数入口显式处理if max_k <= 0: return 0。

再比如 prices 长度为 1，前一天的 -prices[0] 会成为持仓成本，后续没有卖出机会，最终返回 0，这也需要入口处短路：if n < 2: return 0。

5.3 面试和实战中的表达建议

如果是在面试场景中写这道题，建议按这样的节奏表达：先说"这题可以用动态规划，因为每天只有买卖持有三种状态，且最优解依赖于前一天的状态"，接着定义 dp 数组并解释每个维度，然后写转移方程，最后补初始化和循环。即使最后代码有小瑕疵，只要思路清晰、方程正确，评价通常不会差。

我在模拟项目X的训练中观察到，很多学员能把转移方程背得很熟，但被问到"为什么 buy 的时候 k-1, sell 的时候 k 不变"就答不上来。建议把这个问题想透：交易次数在买入时消耗，卖出时只是完成这次已开始的交易。这样解释既严谨，也能让对方感受到你是真的理解，而不是背模板。

5.4 一组实测用例

下面这组用例覆盖了六种常见变体，可以直接用来验证自己的实现是否正确：

我就用这个表格给学员做自测，每道题跑通之后再继续下一个版本，这样能把"理解状态方程"和"验证代码逻辑"分开，不会混在一起。

实际做题过程中，还有一个冷门但有用的观察：一旦你对某个变体的状态定义足够熟悉，就可以在六种变体之间快速切换，因为它们的结构高度相似。你不需要背六套代码，只需要背一套状态转移的"母版"，再根据不同约束增删状态和分支即可。这也是动态规划在股票买卖问题上最有魅力的地方。

最后再分享一个小技巧：把 dp 数组完整打印出来，逐行检查第 i 天的 dp_i_0 和 dp_i_1 是否符合直觉。比如第一天价格 7，第二天价格 1，那 dp_1_1 应该是 -1 而不是 -7，因为最优买点已经更新为第二天。打印日志虽然笨，但排查速度远快于盯着代码空想。这种验证习惯，到了更复杂的动态规划题里同样适用。