企业官网建设流程全解析

这个系列写到第4篇，我终于敢碰动态规划了。前3篇数组、链表、哈希表刷完，热题100里那些“数据结构题”基本不再发怵。但从第4篇开始，话题明显换了一档——力扣（LeetCode）热题100里有几道“买卖股票的最佳时机”，编号121，后面还拖了122、123、188、309、714一大家子。我一开始是拒绝的，看着题解区铺天盖地的状态转移方程，感觉每个字都认识，连起来就不像人话。但这周硬着头皮把六道题全啃下来后，必须承认：股票系列就是动态规划最友好的一道门，整个刷题过程正好踩在“小白的认知斜坡”上。这篇笔记我就用Python3，把从小白视角完整刷这6道题的过程、思路、代码和翻车记录都整理出来，尤其是那些题解区默认你会、但新手根本不知道的细节。

1. 为什么第4篇从股票入手：动态规划最友好的启蒙台阶

1.1 热题100里的股票题其实只有两道“正餐”

先说个容易误会的地方：力扣热题100里真正收录的股票题只有121和122两道。但这两道题所属的“股票六连”在讨论区被合称为炒股系列，我建议一次性全刷掉。原因很简单：只刷121、122，你学会的是两个孤立技巧（一次遍历最小值、贪心累加上升差），但把123、188、309、714接着刷完，你会自然建立起“状态机”这个DP核心思维。状态机这个东西，越到后面越香，热题100后半段的打家劫舍、不同路径、零钱兑换全都要用。六道题的限定条件刚好是一个逐级加码的阶梯：121只能买卖一次，122可以买卖无限次，123最多买卖两次，188最多买卖k次，309卖出后第二天不能买入，714每次交易要交手续费。题目编号看起来乱，但学习顺序按这个阶梯走就可以，从最少限制到最多限制，每一步只引入一个新概念，脑子不会过载。

1.2 为什么说它是小白的DP启蒙台阶

很多人被DP吓退，是因为一上来就遇到“最长递增子序列”“编辑距离”这种状态定义特别抽象的题。股票系列的好处在于：题目本身就是一个生活场景——你是一个股民，每天看价格，决定买、卖还是不动。每天收盘时，你的状态只有两个：手里拿着股票，或者手里没股票。就这么朴素。把这种“每天的状态”记下来，再考虑“从一个状态怎么转移到另一个状态”，这就是状态机。股票题的每个变形，都只是在问：在某种额外规则下，这个状态机该怎么改。学完股票系列，你对“为什么DP能算出全局最优”“为什么需要状态定义”会有一个非常实感的理解，而不是停留在背模板。后面遇到树形DP、区间DP，你会发现底层思考方式完全一样，区别只是状态维度更多、转移条件更复杂。

1.3 我建议的六道题刷题顺序

我自己是按照121 → 122 → 123 → 188 → 309 → 714的顺序刷的，刷完回头看，这个顺序其实是最科学的。121题先体会“用过去的信息优化今天的决策”；122题引入“持有/不持有”两状态，体会状态转移；123题把两状态复制成两份，学会处理“次数限制”；188题把次数参数化，得到通用模板；309题在状态里加一个“冷冻期”分支；714题在转移过程中加一笔手续费。每道题都只在上一步的基础上增加一个变量或一个分支。如果反过来从188开始，大概率会劝退。刷的时候我会在每题下面记录自己的理解，而不是写完AC就完事。尤其是第一次写出的错误状态定义，我会单独记一笔，因为那才是真正属于我的知识盲区。

2. 121题：一次买卖，“历史最低价”就是最朴素的钥匙

2.1 题目要求和最直观的粗暴解法

121题的描述一句话就能说完：给一个数组prices，你只能选择某一天买入，之后某一天卖出，求最大利润。如果赚不到钱，返回0。最直观的解法是暴力枚举：外层循环选买入日i，内层循环选卖出日j（j必须大于i），算prices[j] - prices[i]的最大值。

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

复杂度O(n²)，力扣上n可以达到10^5量级，这个写法会超时。但暴力解一定要先写出来，因为它是后面所有优化的对照基准。我经常用这个暴力版本去对拍未来的优化版本，确保优化不会改错结果。如果你在面试中被问到121题，先给出暴力再优化，本身就是加分项，说明你有“从朴素到高效”的完整思考链路，而不是只会背题解。

2.2 一次遍历：把“买在最低、卖在最高”拆成两步

暴力解慢在重复扫描。仔细想一下：当你在第i天准备卖出时，买入日应该选哪一天？一定是从第0天到第i-1天里价格最低的那天。于是优化思路就出来了：遍历数组时维护一个历史最低价min_price，每到一天就算“如果今天卖，能赚多少钱”，和全局最大利润max_profit比较，然后顺便更新min_price。

class Solution: def maxProfit(self, prices: List[int]) -> int: if not prices: return 0 min_price = prices[0] max_profit = 0 for price in prices[1:]: max_profit = max(max_profit, price - min_price) min_price = min(min_price, price) return max_profit

第一次写这道题有一个特别容易错的顺序问题：先算profit还是先更新min_price。必须先算“今天卖出能赚多少”，再更新min_price。如果顺序反了，当天的价格会被当作买入价，出现“同一天买入又卖出”的错误。虽然这道题里同一天买卖的利润是0，不影响最终答案，但到了更复杂的变形题里，这个顺序会直接让结果出错。我在123题里就因为这个吃过亏，最好一开始就养成正确习惯。还有一个细节：min_price初始化为prices[0]，这样遍历从下标1开始，语义上也是“当前天只能买卖过去天”，整个循环的逻辑闭环。

2.3 用DP语言重新理解121题

只用上面的做法就能AC，但我想多说一句DP视角，因为后面五道题全部依赖它。定义dp[i]为“前i天内能获得的最大利润”，递推式是dp[i] = max(dp[i-1], prices[i] - min_price)。意思很直白：第i天收盘时，要么什么都不干，沿用前i-1天的最大利润；要么把历史最低价买入的股票在今天卖出。每次更新完dp[i]后再更新min_price，保证“历史最低价”用的是前i天的数据。我第一次写DP版本时犯过一个典型错误：把dp[i]理解成“第i天必须卖出时的利润”，结果数组里出现一堆负数还不明白为什么。正确的理解是：dp[i]是一个前缀最优值，记录的是前i天内无论如何操作能达到的最好结果，而不是“今天必须做某个动作”。前缀最优和当天动作，这两个概念区分清楚，DP就算入门一半了。测试用例建议至少跑这么几个：

空数组和单元素是力扣喜欢埋的边界，不能漏。我第一次提交121题时就是漏了空数组，直接IndexError，被测试用例教育了一课。

3. 122题：贪心先手拿下，但状态机才是后面解题的钥匙

3.1 允许无限次交易后，贪心为什么成立

122题跟121的区别只有一个：你可以进行多次交易，但手里最多同时持有一只股票，也就是买入下一只之前必须卖出当前这只。这个条件下，最优策略其实简单到反直觉：只要今天的价格比昨天高，就在昨天买入今天卖出，把这段差价赚到；如果价格下跌，就不操作。把所有上升段的差价累加起来，就是最大利润。

class Solution: def maxProfit(self, prices: List[int]) -> int: profit = 0 for i in range(1, len(prices)): if prices[i] > prices[i - 1]: profit += prices[i] - prices[i - 1] return profit

为什么能这样贪？因为无限次交易下，每一段上升区间都是独立的。你可以把prices[i] - prices[i-1]理解成“第i天比第i-1天新增的利润”，只要这个增量是正的，就纳入收益。价格曲线整体上拍成一个个相邻差值的和，把所有正差值加起来，等价于“在每个局部最低点买入、局部最高点卖出”。这个解法两行代码，看起来已经到头了。但如果你只记住它，到123题就废了——因为一旦限制了交易次数，正差值就不能全部都要，你必须决定“哪几段上升更值得赚”，这个问题贪心就答不上来了。

3.2 状态机：每天收盘时你只有两种身份

122题的DP解法是后面所有股票题的地基。先定义两个状态：empty表示今天收盘时不持有股票，hold表示今天收盘时持有股票。每天都可以做三件事：不操作、卖出、买入。于是有两条转移：今天收盘不持有 = 昨天就不持有（今天没操作），或者昨天持有但今天卖出；今天收盘持有 = 昨天就持有（继续拿着），或者昨天不持有但今天买入。写成代码：

class Solution: def maxProfit(self, prices: List[int]) -> int: empty = 0 hold = float('-inf') for price in prices: new_empty = max(empty, hold + price) new_hold = max(hold, empty - price) empty, hold = new_empty, new_hold return empty

初始化时empty=0，代表一分钱没投、手里也没股票的收益；hold=-inf，因为第一天不可能已经持有股票。每个price循环时用旧值算出新值，再统一赋值。千万别写成先更新hold再更新empty，那样第二行用到的hold已经是本轮的更新值，逻辑就串了。这种“同一轮新旧值混用”的坑，我在后面几道题里反复踩，最终养成习惯：宁可多写两个new_变量，也不要让代码看起来省事。

3.3 为什么这个状态机比贪心更值得学

贪心代码两三行，状态机看起来多好几行，为什么不直接用贪心？因为状态机是可扩展的。贪心解法只在“交易次数无限”时成立，一旦题目改成“最多两次”“最多k次”“冷冻期”“手续费”，贪心逻辑就要大改甚至完全失效。而状态机只需要在转移方程里加状态、加条件，整个框架不变。我给一个小白的判断方法：一道交易类题目能不能用状态机解，就看它是否满足“每个阶段做决策，且决策受之前决策约束”。股票题全部满足。所以趁122题就把状态机焊死在脑子里，后面五道题都是顺着这个骨架填肉。我实测下来，先写完状态机版本再去写贪心，会明显感觉“代码只是想法的投影”，而不是“靠记忆默写答案”。

4. 123与188题：交易次数变成变量，状态机开始“吃不饱”

4.1 123题：把两个状态复制成两份

123题：最多可以完成两笔交易。此时每天收盘时的状态不是两个，而是四个：第一次买入、第一次卖出、第二次买入、第二次卖出。换句话说，状态机里需要维护4个变量：buy1（完成第一次买入后的最大收益，通常是负数，因为买了股票花掉钱）、sell1（完成第一次卖出后的最大收益）、buy2（完成第二次买入后的最大收益）、sell2（完成第二次卖出后的最大收益）。转移顺序是固定的因果链：先第一次买入，才可能第一次卖出；第一次卖出赚到的钱，才可能支撑第二次买入；第二次买入后才有第二次卖出。

class Solution: def maxProfit(self, prices: List[int]) -> int: if not prices: return 0 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 sell2

这段代码我在第一次写的时候栽过跟头，原因是把buy2的转移写在了sell1前面。一旦sell1还没更新，buy2拿到的就是昨天的sell1，等于默认了“第二次买入不能发生在第一次卖出当天”。题目其实允许同一天先卖后买，所以必须保证sell1用本轮新值。这个顺序敏感性问题，在初学阶段几乎一定会遇到，记下来能省很多调试时间。还有一个常见的错误想法：把123题拆成“跑两次121”。我试过，先找整体最大的一段利润，再在剩下的区间里找第二段，这样的局部最优拼不出来全局最优，因为两段交易的最优窗口可能重叠，而重叠时股票交易的约束关系会被破坏。老老实实让四变量同步滚动才是正解。

4.2 188题：k次交易的通用模板

188题把“两次”改成“k次”，四变量就升级成两个数组：buy[j]表示完成第j次买入后的最大收益，sell[j]表示完成第j次卖出后的最大收益。j从1到k。

class Solution: def maxProfit(self, k: int, prices: List[int]) -> int: if not prices: return 0 n = len(prices) if k >= n // 2: profit = 0 for i in range(1, n): if prices[i] > prices[i - 1]: profit += prices[i] - prices[i - 1] return profit buy = [float('-inf')] * (k + 1) sell = [0] * (k + 1) for price in prices: for j in range(1, k + 1): buy[j] = max(buy[j], sell[j - 1] - price) sell[j] = max(sell[j], buy[j] + price) return sell[k]

这条模板有两个关键细节。第一，内层循环j必须从小到大。原因是buy[j]要用到sell[j-1]，而sell[j-1]在本轮中被更新之后，才代表“这一天可以先完成第j-1次卖出，再立刻进行第j次买入”。从小到大保证了这种同一天先卖后买的操作可以被表达。如果从大到小，模板会把所有交易都限制在不同日期，某些测试用例结果会偏小。第二，k >= n // 2时要退化为无限次交易。理由是每次完整交易至少需要两天（买入一天、卖出一天），当k大于等于n//2时，允许的交易次数已经超过实际能进行的最大交易次数，限制形同虚设。此时直接跑122题的贪心，时间从O(nk)降成O(n)，不然k很大的时候会超时。这个剪枝在力扣188题里几乎必考。我一开始没做这个剪枝，k=100000、n=6的用例直接超时，才意识到“理论最大交易次数”这个约束有多关键。

4.3 从188看123，模板越通用越不容易错

刷完188再回头看123，你会发现123完全可以用188模板直接跑：k=2传入，结果就是sell[2]。我后来改掉死记四变量的习惯，统一用188模板解题，正确率反而更高。因为四变量版本里buy1、sell1、buy2、sell2的语义容易搞混，而模板里“第j次买入/卖出”的语义是规整的，出错时只需要盯着j看。刷到这里，我也意识到一个经验：凡是带“最多k次”的题目，先判断k是否超过理论最大值，再决定用DP还是贪心，这是第一件事。第二件事是，画出状态表手推一遍小数据。比如用[2,1,2,0,1]配合k=2，把每一轮结束后的buy[1]、sell[1]、buy[2]、sell[2]全部列出来，跟代码执行结果比对。这一步大概花十分钟，但能帮你把整个状态机的运行机制彻底钉进脑子里。

5. 309与714题：冷冻期和手续费，状态机的两个“改锥”

5.1 309题：多一个状态去记录“昨天卖过”

309题在122题基础上加了冷冻期规则：卖出股票后，第二天不能买入。翻译成人话：今天要想买入，必须保证昨天没有卖出。所以“不持有股票”这个状态必须拆成两种——一种是“今天是不持有的普通状态，随时能买”，另一种是“今天刚卖出，明天才能买”。我定义三个状态：hold（今天收盘时持有股票）、sold（今天收盘时不持有股票，且今天刚卖出，进入冷冻期）、rest（今天收盘时不持有股票，且今天没有卖出，可以正常买入）。转移关系：hold[i] = max(hold[i-1], rest[i-1] - prices[i])，继续持有，或者从rest状态买入；sold[i] = hold[i-1] + prices[i]，只能从持有状态卖出；rest[i] = max(rest[i-1], sold[i-1])，保持休息，或者冷冻期结束后变成可交易状态。

class Solution: def maxProfit(self, prices: List[int]) -> int: if not prices: return 0 n = len(prices) hold = [0] * n sold = [0] * n rest = [0] * n hold[0] = -prices[0] for i in range(1, n): hold[i] = max(hold[i - 1], rest[i - 1] - prices[i]) sold[i] = hold[i - 1] + prices[i] rest[i] = max(rest[i - 1], sold[i - 1]) return max(sold[-1], rest[-1])

sold[i] = hold[i-1] + prices[i]这一行是冷冻期题最容易写错的地方。很多新手会写成sold[i] = hold[i] + prices[i]，这等于允许“今天买入今天卖出”，完全破坏了状态语义。冷冻期题的关键就是记住：卖出动作发生前，你手里必须已经持有股票，而持有股票的收益是昨天结束时的hold值，不是今天买入后的值。用滚动变量可以把这个三维数组压缩成三个变量，但初期建议先写数组版本，配合打印中间值看清楚每个状态的变迁。我发现能把这题的三状态手推清楚，对理解“状态之间互相制约”很有帮助，后面做题会越来越顺。

5.2 714题：把手续费写进卖出分支

714题只改了一个条件：每完成一笔交易要支付fee手续费，不限制交易次数。解法就是在122题的状态转移里，卖出时扣掉手续费：empty[i] = max(empty[i-1], hold[i-1] + prices[i] - fee)，卖出并扣手续费；hold[i] = max(hold[i-1], empty[i-1] - prices[i])，买入不变。

class Solution: def maxProfit(self, prices: List[int], fee: int) -> int: empty = 0 hold = float('-inf') for price in prices: new_empty = max(empty, hold + price - fee) new_hold = max(hold, empty - price) empty, hold = new_empty, new_hold return empty

手续费放在卖出时扣还是买入时扣，最终结果一样，但必须固定一种写法，不能混用。我个人的习惯是放在卖出时扣，因为“收益 = 卖出收入 - 买入成本 - 手续费”的语义更顺。714题真正恶心的是贪心解法。网上很多版本维护一个买入价buy_price，当prices[i] > buy_price + fee时卖出，可是卖出之后如果价格继续涨，还要回头补差价，实现细节很容易漏。我一开始照着贪心思路写，连续WA三次，后来换成DP状态机一次通过。所以我的建议是：手续费题目直接用DP，别贪。状态机虽然看起来多写几行，但转移语义清晰，调试成本低得多。

5.3 六道题打完之后的状态机统一视图

现在我回过头看，六道题其实共享同一个骨架：状态 = 手里是否持有 + 额外约束（交易次数/冷冻期/手续费）；转移 = 买入、卖出、不操作三选一；额外约束 = 修改状态集合或转移条件。121题单次交易，只在买入分支上加一次；122题去掉次数限制；123/188题状态乘以交易次数维度；309题把“不持有”拆成“可买”和“冷冻”；714题在卖出分支扣钱。每一道题都只是在这个骨架上打一个小补丁。小白的最大误区是把六道题当成六种解法去背，背完就忘；而一旦理解成“同一个状态机的补丁序列”，你会发现只需要记住那三四行转移方程，其他变形推一推就出来了。

6. 六道题刷完：小白最该避开的几个坑和我的复盘

6.1 坑一：初始化变量时不懂每个值在说什么

第一次写122题，hold为什么初始化为0而不是-prices[0]，或者为什么不是浮点负无穷？如果不理解初始化含义，后面所有代码都是空中楼阁。我踩过的具体问题是：把hold初始化为0，结果第一轮就允许“空手买入后继续卖出”，状态错乱。正确的做法是：每个变量初始化之前，先在注释里写明它的语义，例如“hold表示今天结束时持有股票的最大收益；初始时不存在持有股票的状态，所以设为负无穷”。语义清楚之后，初始化就不会瞎猜。这个习惯从股票系列带到所有DP题，都是最有效的防错手段。

6.2 坑二：循环里新旧值互相污染

这个问题前面多次提到，再集中说一次。凡是一轮要更新多个状态，最稳妥的写法是先把所有新值算出来，再统一赋回。别图省事在更新链路里直接用变量本身。我自己DEBUG最长的一次，就是122题少写了两个new_变量，结果每次输出都比预期小，查了半天才发现是第二行更新用到了第一行的新值。代码里看似少写两行，但代价是半小时的排查时间。写代码时稍微啰嗦一点，其实是在给未来的自己省事。

6.3 坑三：边界用例永远不能省

空数组、单元素、全涨、全跌、平盘，这五个用例每个题都要跑一遍。我在121题上吃过空数组的亏：直接取prices[0]会报IndexError。前面列的那个表格，我每次写新解法都会先跑一遍，通过了再提交。力扣的测试用例从来不心慈手软，有时候一个隐藏的空数组就能让你WA到怀疑人生。

6.4 坑四：只背代码，没有手推过小数据

123题的官方题解里四行转移，看起来人畜无害，但你不手推一遍根本不知道buy2和sell1之间的因果关系。我推荐一个笨办法：拿[1,5,2,6]这种小数组，手工走一遍每轮迭代后的所有变量值，然后跟程序print出来的结果对比。这个习惯花的时间不多，但能治“看懂了但不会写”的毛病，而且能在面试时帮你快速定位状态定义哪里有问题。手推过一轮之后，你会发现那几行转移方程从“天书”变成了“账本”，每一步都有明确的业务含义。

6.5 坑五：没有“对拍”意识

对拍是算法题里一个非常实用的手段：写一个慢但绝对正确的暴力版本，再写一个快版本，然后用随机小数组反复对比两者的输出。我在刷股票系列时，每个优化版本都会保留一个暴力版本做对拍。对拍脚本其实非常简单，核心思路就是构造随机输入，比较两个版本的输出是否一致，下面是我常用的最小脚本框架：

import random def maxProfit_brute(prices): # 暴力实现，绝对正确 ans = 0 for i in range(len(prices)): for j in range(i + 1, len(prices)): ans = max(ans, prices[j] - prices[i]) return ans def check(): for _ in range(1000): n = random.randint(1, 8) prices = [random.randint(1, 10) for _ in range(n)] a = maxProfit_brute(prices) b = maxProfit_fast(prices) if a != b: print(prices, a, b) return print("all ok") check()

对拍跑通一次，你对优化版本正确性的信心会完全不同。这个小技巧适用于所有DP题，强烈建议养成。尤其当你改了某个状态转移公式，不确定是不是“等价变形”时，跑一遍随机对拍比对着屏幕瞪半小时有用得多。

6.6 热题100的节奏：股票系列刷完下一步是什么

刷完这六道题，我对热题100里DP类题目的恐惧感明显降低。后续建议把53. 最大子数组和、70. 爬楼梯、198. 打家劫舍、322. 零钱兑换这些DP基础题顺着刷完，你会发现状态转移的思想是一脉相承的。我在热榜上也看到不少人在搜“力扣热题100 python”“力扣刷题攻略”，说明大家卡的位置差不多。这两天还有个1875将雇员相同的分组挂在热榜上，我点进去看了一眼，属于分组计数的类型，和DP不是一个专题，我打算放到排序/哈希那一阶段再单独啃，避免状态机和分组统计两套思维混在一起。

最后说点个人体会：股票六连题刷下来，我最大的收获不是会写这几道题，而是终于知道动态规划是怎么“想出来”的——先定义状态，再画转移，最后查边界。这个流程以后遇到任何新DP题都能复用。如果你也是小白，别怕这类题，把它们当成同一个状态机的六个补丁，一个一个打上，你会发现所谓的DP并没有传说中那么高不可攀。