企业官网建设流程全解析

做算法题的人，应该都绕不开“买卖股票的最好时机”这组题。它是动态规划入门阶段特别典型的题目，几乎每个刷题平台都会收录，LeetCode 上编号 121、122、123，很多公司笔试面试也喜欢换着花样出。这类题看起来就是“给一串价格，求利润最大”，但三个版本的限制条件完全不同：I 是只能买卖一次，II 是能无限次买卖，III 是总共最多买卖两次。也就是这几个看似相似的版本，逼着你从一维DP、二维DP一直升级到带交易次数维度的三维DP。

这篇内容我按自己的刷题顺序来写，从第一印象、状态定义、转移方程，到代码实现、边界处理、常踩的坑，再到最后怎么把这套模型迁移到其他题目上。对于刚接触动态规划的人来说，这组题是很好理解“状态机DP”和“线性DP”的入口；对于已经刷过几十道题的老手，我也把空间压缩和交易次数边界问题单独拉出来聊，算是给自己做个复盘。

1. 先看清这三个题到底在问什么

很多人一上来就把 I / II / III 混着刷，结果思路互相干扰。其实这三兄弟虽然都是买卖股票，但规则和难度完全不一样，先把题目要求抠清楚，后面才不会跑偏。

1.1 交易规则差异：一次、无限次、最多两次

第 I 题（LeetCode 121）：给定一个数组，价格按天排列，你只能选择某一天买入，后面的某一天卖出，最多完成一笔交易。注意这里不能“先卖后买”，也不能同一天既买又卖（虽然同一天买卖利润为零，但题目默认持有股票才能卖）。说白了就是找一个买入日和卖出日，让prices[sell] - prices[buy]最大，且买入日必须早于卖出日。

第 II 题（LeetCode 122）：不限制交易次数，但你在手上有股票的时候不能再买入，也就是说任何时刻最多只能持有一股。可以买完卖、卖完再买，只要操作顺序合法，利润可以不断累积。

第 III 题（LeetCode 123）：限制了交易次数，整个时间段内最多只能完成两笔交易。这里“一笔交易”通常理解为一个买入加一个卖出，并且同一时间只能持有一股。难点在于两笔交易之间可能有一段时间的空仓“休息期”，也可能第二笔紧接着第一笔卖出的下一天就买入。

这三道题正好构成一个递增的题干复杂度：I 最简单，II 次之，III 需要显式记录交易次数。如果你只背答案不分析，很容易把 II 的贪心写法套到 III 上，那就完全错了。

1.2 为什么看起来一样，解法完全不同

因为 I、II、III 对应的约束是一个比一个强的决策过程。I 相当于问你“最低点买、最高点卖”，但有个隐藏限制：最低点必须在最高点之前。所以不能直接max(prices) - min(prices)，必须一边遍历一边维护历史最小值。II 则变成了“每个上涨段都吃”，所以贪心是合法的：只要今天的价格比昨天高，就认为昨天买入、今天卖出，利润累加。III 多了交易次数限制，贪心就不再可靠了，因为可能为了多赚一次而牺牲次数，但你最多两笔，是需要在局部决策之间取舍的。

这时候动态规划的“状态转移”优势就体现出来了。不管是 I、II 还是 III，都可以统一建模成每一天“手里持有股票”还是“手里没有股票”这两个状态，只是 III 需要在状态里额外增加“已完成交易次数”。一旦把决策过程变成状态转移，三种题目只是同一个模型的参数配置不同而已。

2. 动态规划模型：从“决策过程”到状态机

2.1 买卖股票为什么天然适合DP

因为股票价格是一个按时间排列的序列，你每天能做的决策只有三种：买、卖、什么都不做。每一天的最高收益取决于前一天的状态和当天的价格，这正好符合动态规划要求的“无后效性”：第 i 天的决策只影响第 i 天以后的结果，一旦确定了第 i 天持有的股票数量和已完成的交易次数，之前具体哪天买的、哪天卖的都不重要了。

所以这类问题的本质不是求某个具体日期，而是求“第 n 天结束时，在某个状态下能获得的最大收益”。用大白话说就是：今天你是空仓还是持股，赚了多少，明天在这个基础上继续做选择。

我一开始学的时候，容易把它和“递推求最大利润”混淆。比如 I 可以定义dp[i]表示前 i 天最多赚多少钱，但这样定义很难处理“你手里有没有股票”这个约束。所以更自然的是加一维，用dp[i][0]表示第 i 天结束后手里没有股票的最大利润，dp[i][1]表示第 i 天结束后手里还持有股票的最大利润。

2.2 状态机的标准建模思路

“状态机”这个名字听起来唬人，其实就是一个二维表格：每一天、每个状态下记录一个最优值。就拿 II 来说，两个状态之间的转移关系是：

• 如果第 i 天结束后手里没有股票（空仓），可能前一天就空仓，今天什么都不做；也可能前一天持股，今天把股票卖掉。所以取这两种路径的较大值。
• 如果第 i 天结束后手里持有股票，可能前一天就持股，今天继续拿；也可能前一天空仓，今天买入。买入需要付出当前价格，所以要用空仓利润减去prices[i]。

写出来就是：

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

这个结构就是状态机：0 -> 0是不操作，1 -> 0是卖出，0 -> 1是买入，1 -> 1是持有不动。画成图就是四个有方向的箭头，代码只是把箭头两端取最大值。

对于 I 来说，因为只能交易一次，你不能从“空仓并已经交易过”的状态再买入。所以它的dp[i][1]转移往往写成max(dp[i-1][1], -prices[i])，意思是“要么继续保持昨天持有的状态，要么在第 i 天新买入”。这里没有dp[i-1][0] - prices[i]，因为 I 要求一旦卖出了就不能再买入，而dp[i-1][0]里既包含了“从未买过”也包含了“已经卖完空仓”的情况，直接用它买入就会导致多次交易。

对于 III，我们再加一个维度记录“已经发生了多少次交易”。这时状态变成dp[i][k][0/1]，k的取值范围从 0 到 2，表示“已经完成或正在进行第 k 笔交易”。状态转移把买卖路径做对应调整，就是同一个状态机的三维版本。

2.3 和01背包等经典DP的关系

很多人会问：买卖股票和 01 背包有什么关系？它们都属于线性 DP，但决策模型有区别。01 背包是“每件物品选或不选”，选与不选直接决定价值；股票问题是“每天买、卖、不操作”三种动作，并且买和卖是成对出现的约束。但从记忆化搜索或者状态定义的角度来看，它们的核心思想一致：枚举每一个决策点，用之前计算好的子问题结果更新当前状态。

做动态规划题，最重要的是先搞明白“有哪些状态”，而不是急着写转移方程。拿这个思路去看洛谷的动态规划题目单，会发现很多题都是“状态机套外壳”：打家劫舍是在“偷当前家/不偷当前家”之间切换，完全平方数是在“选哪个平方数”之间决策，区间DP是在“枚举分割点”。股票 III 可以说是状态机 DP 里最直观的入门题，因为交易次数维度能让你切切实实感受到多一维状态就多一重决策。

3. 分题破解：从一维到两维再到三维

下面我按 I、II、III 逐个推状态转移方程，并给出 Python 代码。代码尽量保持统一风格，方便对比。

3.1 第I题：一次交易的最优时机

状态定义：

dp[i][0]表示第 i 天收盘后，不持有股票的最大利润。

dp[i][1]表示第 i 天收盘后，持有股票的最大利润（注意这里的“利润”是负收益，因为买入付了钱）。

转移方程：

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

第二个式子里为什么是-prices[i]而不是dp[i-1][0] - prices[i]？因为只能交易一次，所以买入只能发生在“从未买过”的状态下。如果从dp[i-1][0]买入，那dp[i-1][0]可能是已经完成一次交易后的空仓，会引入第二笔交易。

初始化：

dp[0][0] = 0，第 0 天没买没卖，利润为 0。

dp[0][1] = -prices[0]，第 0 天买入，利润为负的当天价格。

答案：

dp[n-1][0]，也就是最后一天不持有股票的最大利润。持有股票在最后一天通常不会比空仓更优，但直接取max(dp[n-1][0], dp[n-1][1])也安全。

参考代码：

def maxProfit(prices): n = len(prices) if n == 0: return 0 dp = [[0, 0] for _ in range(n)] dp[0][0] = 0 dp[0][1] = -prices[0] for i in range(1, n): dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]) dp[i][1] = max(dp[i - 1][1], -prices[i]) return dp[n - 1][0]

这个解法的时间复杂度 O(n)，空间复杂度 O(n)。其实还能优化成 O(1)，但刷题时我更推荐先写二维数组，因为不容易出错，等 AC 了再压缩空间。

也可以不维护dp[i][1]，直接用一个变量记录“历史最低价格”，然后每天计算prices[i] - min_price。但 DP 的写法好处是能平滑扩展到 II 和 III。

3.2 第II题：无限次交易的累计利润

状态定义：

和 I 一样，dp[i][0]空仓，dp[i][1]持股。只是买入限制去掉，允许反复交易。

转移方程：

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

这次买入用的是dp[i-1][0] - prices[i]，因为只要你手里没有股票，就可以再买入，无论之前做过多少笔交易。

初始化：

与 I 相同，dp[0][0] = 0，dp[0][1] = -prices[0]。

答案：

dp[n-1][0]。

参考代码：

def maxProfit(prices): n = len(prices) if n == 0: return 0 dp = [[0, 0] for _ in range(n)] dp[0][0] = 0 dp[0][1] = -prices[0] for i in range(1, n): dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]) dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]) return dp[n - 1][0]

这里有个很常见的争议：如果价格一直下跌，是不是可以不买，利润为 0？是的，dp[i][0]的初值 0 保证了你始终可以选择“什么都不干”，所以答案为 0 是合法的。

3.3 第III题：两次交易的阶段控制

状态定义：

dp[i][k][0]表示第 i 天结束后，已经完成了 k 笔交易，且当前不持有股票的最大利润。

dp[i][k][1]表示第 i 天结束后，已经发生了 k 笔交易，且当前持有股票的最大利润。

这里的 k 的取值是 0、1、2。怎么理解“已经发生了 k 笔交易”？

我习惯把“买”当作一次交易的开端，k 在买入那一刻加 1；卖出不计入交易次数，因为它只是结束当前这笔交易。所以你持有股票时，k 代表的是“正在做第 k 笔交易”中的那 k 个已开启交易数；空仓时，k 代表的是“已经完整结束的 k 笔交易”。

转移方程：

对于空仓状态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 笔交易，然后今天买入一笔新交易，从而变成已发生 k 笔交易。买入会增加交易次数：

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

初始化：

dp[0][0][0] = 0，第 0 天空仓且没有交易。

dp[0][0][1] = -inf，第 0 天不可能持有股票且完成 0 笔交易。

dp[0][1][0] = -inf，第 0 天不可能已经完成 1 笔交易。

dp[0][1][1] = -prices[0]，第 0 天买入第一笔，表示“开启第 1 笔交易”。

dp[0][2][0] = -inf，第 0 天不可能完成 2 笔交易。

dp[0][2][1] = -inf，第 0 天不可能开启第 2 笔交易。

答案：

max(dp[n-1][0][0], dp[n-1][1][0], dp[n-1][2][0])。因为最后一天手里肯定不持有股票，而且交易次数不会超过 2。

参考代码：

def maxProfit(prices): n = len(prices) if n == 0: return 0 # dp[k][0/1] # 初始化，用 -inf 表示不可能状态 dp = [[-float('inf'), -float('inf')] for _ in range(3)] dp[0][0] = 0 dp[1][1] = -prices[0] dp[0][1] = -float('inf') dp[1][0] = -float('inf') dp[2][0] = -float('inf') dp[2][1] = -float('inf') for i in range(1, n): # 因为要用到上一层的前一天数据，所以需要从旧值推导 # 这里用临时变量存前一天的值 old = [row[:] for row in dp] for k in range(1, 3): dp[k][0] = max(old[k][0], old[k][1] + prices[i]) dp[k][1] = max(old[k][1], old[k - 1][0] - prices[i]) # k=0 时不能买入，也不能卖出（因为没买过） dp[0][0] = old[0][0] # 持有状态 k=0 在第 i 天只能延续，不可能从 k=-1 买入而来 dp[0][1] = old[0][1] return max(dp[0][0], dp[1][0], dp[2][0])

这个代码我故意保留了完整的三维版本直接压缩成dp[k][0/1]二维数组，再用一个old拷贝前一天状态，为的是把维度压缩逻辑讲清楚。实际刷题更推荐写成五个变量，或者直接开三维数组，逻辑更直白。

3.4 空间优化技巧

如果开三维数组dp[n][3][2]，空间是 O(3n)，也没多大问题。但有时候题目会把价格长度拉长到十万、百万，滚动数组就很有必要。空间优化的核心是：第 i 天只依赖第 i-1 天的状态，因此可以只保留两行。

刚才代码里已经演示了“拷贝旧值”的方式，另一种更优雅的写法是用五个变量：

def maxProfit(prices): n = len(prices) if n == 0: return 0 # buy1 表示完成第1笔买入后的利润，sell1 表示完成第1笔卖出后的利润 # buy2 表示完成第2笔买入后的利润，sell2 表示完成第2笔卖出后的利润 buy1, sell1 = -prices[0], 0 buy2, sell2 = -prices[0], 0 for price in prices[1:]: buy1 = max(buy1, -price) sell1 = max(sell1, buy1 + price) buy2 = max(buy2, sell1 - price) sell2 = max(sell2, buy2 + price) return max(sell1, sell2)

这里的顺序非常讲究：必须先更新 buy1，再更新 sell1，再更新 buy2，最后更新 sell2。因为 sell2 依赖新的 buy2，buy2 依赖新的 sell1，sell1 依赖新的 buy1。如果顺序反了，比如先更新 buy2，用到的 sell1 还是旧值，那就会忽略“第一笔卖出”后立刻做第二笔买入的情况。

这个变量版其实就是三维 DP 滚动数组压缩到极限的结果。我个人建议：初次接触务必先写三维 DP，能够观察k维度如何变化，熟悉之后再写变量版。面试时如果直接甩变量版本，面试官有时反而看不清楚你的思路，不如先讲三维状态机，再提一句“可以压缩到常数空间”。

4. 实现落地：代码、边界与坑

4.1 初始化与答案取值

初始化是这类题最容易翻车的地方。我总结了三条原则：

第一，用-inf表示“不可能状态”，而不是用 0。比如dp[0][1][0]不可能在第 0 天完成一笔交易并空仓，如果初始化成 0，后续转移会把不可能状态激活，答案就会错。

第二，dp[0][0][0] = 0是所有状态的起点。买入第一笔前，利润为 0，这叫“现金为 0”的初值。

第三，答案不一定只在某个固定状态。III 的答案应该是所有k值下空仓状态的 max，因为如果第一笔交易亏了，你完全可以只做 0 笔或者只做 1 笔，所以不能用dp[n-1][2][0]直接返回，要把dp[n-1][0][0]和dp[n-1][1][0]也纳入比较。

这三个原则在后续做股票 IV、含手续费、含冷冻期时同样适用。

4.2 常见错误与调试记录

下面是我实际刷题时踩过的坑，逐个列出来。

错误一：II 的买入用了dp[i-1][0] - prices[i]，但 I 也照抄。I 允许一次交易，如果你用dp[i-1][0]买入，那么dp[i-1][0]可能来自已经卖出一次后的状态，就会出现“卖了再买”的非法操作。I 必须用-prices[i]买入，或者单独记录“从未交易状态”的现金 0。

错误二：III 的 k 维度语义混乱。如果 k 表示“已经卖出过几次”，那么买入时不增加 k，卖出时增加 k，转移方程会变成另一套。很多题解的 k 定义不一样，看起来代码差不多，但边界完全不同。我建议固定一种语义：k 表示“买入/开启交易的数量”，买入加一，卖出不变。这样初始化更直观，而且买股票时从k-1转过来，天然禁止了“卖后再买”的跨次数操作。

错误三：使用滚动数组时，忘记保存旧值。在三维 DP 压缩成二维数组时，如果直接更新dp[k][0]和dp[k][1]，后面的dp[k][1]可能用到的是已经被覆盖的dp[k][0]或dp[k][1]，导致第 i 天状态被同一天状态污染。解决方法一是用old = dp.copy()，方法二是倒着更新 k（从大到小），但倒序不一定好理解，我前期的做法是直接写三维数组，等空间超限再优化。

错误四：忘了价格数组可能为空。if not prices: return 0虽然简单，但漏了就会数组越界。这类题目边界条件必须要写。

错误五：II 用贪心但解释不清楚。II 的贪心写法确实更短：

return sum(max(0, prices[i] - prices[i - 1]) for i in range(1, len(prices)))

但面试时如果先用贪心解释，可能无法自然过渡到 III 的 DP。所以我建议面试时统一用 DP 思路，平时练习也可以两种都写，体会差异。

4.3 常见问题速查表

5. 举一反三：这套模型还能刷哪些题

5.1 从股票到打家劫舍

打家劫舍（LeetCode 198）的模型和股票 II 非常像。打家劫舍的核心是“相邻两家不能同时偷”，所以状态可以定义成dp[i][0]表示第 i 家不偷的最大金额，dp[i][1]表示第 i 家偷的最大金额。转移：

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

这不就是状态机吗？“偷”和“不偷”两个状态，禁止从“偷”状态直接转移到“偷”状态。很多线性 DP 都能套这个模板。你在洛谷的动态规划题单里会看到大量这种“相邻冲突型”题目，做多了就能一眼识别出状态机。

5.2 从股票到01背包

01 背包问题的核心是“选或不选”，它本质上也是两个状态：选第 i 件物品、不选第 i 件物品。但它是二维决策（容量、物品编号），而股票问题是时间维度加上持有状态。两者都遵循 DP 的公共方法论：

• 把问题拆解成多个阶段；
• 每个阶段定义少量关键状态；
• 用转移方程描述阶段之间的变化；
• 答案从最终状态的候选值中取最优。

所以做动态规划题，不用死记公式，关键是训练自己“找状态”的能力。股票 III 的三维 DP 就是一个很好的例子：一旦你能自然地写出dp[i][k][0/1]，再看 LeetCode 188（最多 k 次交易）就很容易理解，只是把 k 改成一个参数而已；再看 309（含冷冻期）也很简单，多一种“冷冻”状态罢了；714（含手续费）则是在卖出时扣一个手续费。

5.3 我的实战体会

我在刷 hot100 动态规划题时，最受益的就是“状态机”这个思维框架。以前觉得 DP 玄学，后来发现只要把每一步的“状态”先列出来，转移方程其实是顺势而为。买卖股票 I-II-III 正是练习这个思维的好材料：从一个状态到两个状态，从两个状态到六个状态，每次只是多一个维度，代码结构完全不变。

有一些细节我每次都会提醒自己：

第一，为了面试时表达清晰，优先写可读性高的代码，空间优化放到最后提。直接写出三维数组能说明白状态含义，比一开始就上五个变量更能打动面试官。

第二，交易次数 k 的语义要讲清楚。我倾向于“开启交易才算一次”的定义，因为在有冷冻期和手续费的变体题目中，这个定义更贴合直觉：买入触发交易费用，卖出才可能进入冷冻期。

第三，不要忽略“什么都不做”的路径。很多状态转移里，dp[i][0] = max(dp[i-1][0], ...)前面那一项就是“什么都不做”。它保证了最终答案至少为 0，也保证了空仓状态可以一直延续。

如果你现在刚起步，建议按这样的顺序练：先拿 I 题手写二维 DP，把思路理顺；再把 I 题改成 II 题，体会买入状态从-prices[i]变成dp[i-1][0] - prices[i]的原因；最后做 III 题，给二维表加一个 k 维度。这样由浅入深地走一遍，比一次性背五个变量的答案要扎实得多。