1. THREE问题的本质一次错位匹配的收益博弈在聊动态规划之前我建议先把这个THREE对应的场景彻底想清楚。很多人在LeetCode上调这类题时第一反应是“这不是贪心吗”但真正动手写状态转移方程就会发现贪心最多只能做到局部最优一旦交易窗口重叠贪心结果就会和后验最优解差出一个量级。我自己第一次接触这道题时就是在贪心方案上踩了一下午最后老老实实回到DP才算彻底弄明白。这里提的“动态规划THREE——DP”实质上对应一个很经典的模型给定一段价格序列最多允许完成三次买卖买入、卖出各算一次要求最终收益最大。注意两个隐藏约束一是交易必须按时间顺序执行也就是说你不能在第二次尚未卖出之前就买入第三次二是不能同时持有多笔仓位即任意时刻手上要么握有一支股票要么空仓等待。这两个约束决定了问题天然适合用状态机来刻画而不是简单的数学公式。那这个问题为什么值得单独拆出来讲原因在于两层递进关系。第一它是限定最多K次交易类问题的特例把K3代入通用模板很多人的代码会出现数组越界或者状态错乱原因就在于没有理顺“第几次交易”的下标语义。第二THREE的规模恰好跨过了贪心的适用范围——交易次数不算太少价格波动又不像日常币价那样高频用三维DP才是可解释、可扩展、可验证的正道。如果你是为了面试刷题掌握了这一题的通解后面迁到K次、无限次、含冷却期的变体都有迹可循。下面我会沿着四个维度展开先给出问题核心的状态定义与递推公式再用Java代码逐一落地第三个部分说优化途径与常见坑最后做一些实测对比和扩展思考。全文提到的代码我都用标准Java语法写IDE直接用任意版本都行。2. 状态定义与递推关系为什么是“2 × 3 × n”而不是“3 × n”2.1 第一层维度持仓状态先想一个最朴素的问题站在某一天我手上有什么答案只有两个——要么空仓没有股票要么持仓持有一股。很多初学者会忽略这个维度直接定义一个dp[i]表示第i天结束时的最大收益结果发现没办法表达“我今天到底是卖了还是没卖”。实际上任何带买卖约束的DP题都必须在状态里显式标出“手上有没有货”否则转移关系就是残缺的。我把这个维度叫hold取值0或10代表空仓1代表持仓。可能有人觉得用布尔值更优雅但在Java里我用int数组因为后面要加交易次数维度int会更好处理索引。2.2 第二层维度已完成交易笔数题目限定最多三次交易那我必须在状态里知道“现在已经完成了几次完整的买卖”。这里存在一个非常容易混淆的语义当前这笔买卖动作到底算在哪一次头上我用的定义是k表示“已经完成”的交易次数范围为0到3。买入动作发生时不算完成卖出动作发生时才算完成一次。因此等号的右边会出现dp[i-1][k-1][0] - price[i]这种表达式表示“在第k-1次交易结束后空仓然后在第i天买入开启第k次交易此时尚持有股票、已完成的交易次数仍是k-1”。这个语义是整套递推公式的灵魂。如果定义成“正在进行第几次交易”你会发现卖出那一步的状态更新非常别扭因为你不知道应该把k加1还是保持原样很容易写出混淆代码。2.3 第三层维度时间时间维度自然是价格数组的下标我用i表示第几天。注意在Java实现里我会让 i 从1开始计数price[0]返回第1天的价格这样能避免大量的i-1越界判断。于是整体状态是一个三维数组dp[i][k][hold]含义是到第i天收盘时已经完成k次交易并且当前处于hold状态的最高收益。设计成三维不是因为问题真的多复杂而是这样最容易把逻辑拆开正确性也最容易一眼验证。2.4 转移方程从“今天能做什么”出发站在第i天我能做的事情只有三类什么都不做、买入、卖出。针对不同状态转移关系如下如果今天结束时是空仓hold0什么都不做延续昨天的空仓状态收益不变如果昨天持仓今天卖出完成一次交易收益加上今天的价格。公式为dp[i][k][0] max(dp[i-1][k][0], dp[i-1][k-1][1] price[i])。这里的k-1意味着“从第k-1次交易完成后的持仓状态过来”一旦卖出交易次数完成数就变成了k。如果今天结束时是持仓hold1什么都不做延续昨天的持仓状态如果昨天空仓今天买入开始一笔尚未完成的交易但要扣除今天价格作为成本。公式为dp[i][k][1] max(dp[i-1][k][1], dp[i-1][k][0] - price[i])。这里有个细节dp[i-1][k][0] - price[i]中的k保持不变意思是我在空仓且已完成k次交易的状态下买入此时手中的股票属于“第k1次交易”的过程中但尚未完成所以已完成次数依然是k。只有等到未来某天卖出这笔状态才会跳到dp[...][k1][0]。这组递推公式就是从二维股票DP只允许一次交易扩展到K次的自然延伸。写代码时只要严格按住这个语义下标就不会乱。2.5 初始化边界条件是DP的一半生命线初始化我习惯分三部分处理dp[0][k][0]第0天实际上还没开始空仓收益为0。注意这个0是“合法”的初始状态表示还没做过任何事。dp[0][k][1]第0天持仓这在现实中不可能所以必须设置成极小值比如Integer.MIN_VALUE / 2防止后续max运算把无效状态带入。dp[i][0][0]任意一天如果一次交易都没完成且空仓收益恒为0。这类状态不用计算直接等于0。为什么要除以2而不是直接用Integer.MIN_VALUE因为递推公式里有减法dp[i-1][k][0] - price[i]如果dp[i-1][k][0]本身就是MIN_VALUE减去一个正数会溢出变成正数直接把整个DP数组污染掉。这是我早期debug最痛苦的一件事现在写任何带负无穷初始化的DP都习惯用MIN_VALUE/2。3. Java代码落地三维DP方案的完整实现3.1 基础版本直观、可读、跑得通直接上代码我会在注释里标出每个关键分支的语义public class StockTradeIII { public int maxProfit(int[] prices) { int n prices.length; if (n 0) { return 0; } int K 3; // dp[i][k][0]第i天结束已完成k笔交易当前空仓 // dp[i][k][1]第i天结束已完成k笔交易当前持仓 int[][][] dp new int[n 1][K 1][2]; // 初始化第0天不可能持仓 for (int k 0; k K; k) { dp[0][k][0] 0; dp[0][k][1] Integer.MIN_VALUE / 2; } // 第i天从1开始对应prices的第i-1个元素 for (int i 1; i n; i) { int price prices[i - 1]; // k0时空仓收益恒为0持仓不可能 dp[i][0][0] 0; dp[i][0][1] Integer.MIN_VALUE / 2; for (int k 1; k K; k) { // 空仓状态要么继续空仓要么从持仓卖出 dp[i][k][0] Math.max(dp[i - 1][k][0], dp[i - 1][k - 1][1] price); // 持仓状态要么继续持仓要么从空仓买入 dp[i][k][1] Math.max(dp[i - 1][k][1], dp[i - 1][k][0] - price); } } // 最终答案最后一天完成不超过3次交易且空仓 return dp[n][K][0]; } }这个版本的时间复杂度是 O(n×K)空间复杂度是 O(n×K)。K3时基本就是 O(3n)完全可接受。dp[i][0][1]我在循环里直接赋MIN_VALUE/2是为了防止后续买入分支用到一个离谱的初始值。可能有读者会问为什么dp[n][K][0]就是答案而不是在dp[n][k][0]里取max因为K3是“最多三次”中的上限递推公式允许空仓状态一直延续什么都不做所以k3的状态天然囊括了更少交易次数的情况。这点非常关键很多人的贪心错误就来自于总觉得“交易次数越多越好”但实际递推里不做任何操作也能把之前的收益带到更高k的状态里。3.2 一个容易写错的地方循环里的k0分支我在前面代码里对dp[i][0][0]直接赋0很多人会漏掉这个赋值导致后续k1的买入分支读到上一轮残留的脏数据。因为在二维数组复用的情况下如果不显式覆盖dp[i][0][0]可能保留第i-1天残留的旧值。所以每次进入新的天数先把k0的上下两个状态写死再进入k循环这是防御性编程的好习惯。3.3 测试用例验证把正确性焊死拿一个经典序列[3, 2, 6, 5, 0, 3]来验算。理论上最大收益是第2天买价格2、第3天卖价格6收益4第5天买价格0、第6天卖价格3收益3合计7。跑一遍上面的代码输出7。再拿一个下降序列[7, 6, 4, 3, 1]答案应为0代码输出0。这两个用例基本能确认递推公式在语义上没有硬伤。为了更稳我建议你再测一个升序序列[1,2,3,4,5]。直观上最多买卖三次最强策略可以是1买2卖、2买3卖、3买4卖合计最大收益其实等价于第五天价格减第一天价格如果允许一次交易完成全部增值答案是4。三次交易的上限不会让收益变得更多因为升序中每次低买高卖的总和与一次持满是一样的。代码输出也确实是4。4. 空间优化与状态压缩把三维数组压成一维滚动4.1 为什么值得优化三维数组版本好懂但很多面试场合会追加一句“能否把空间复杂度降到O(1)”这就要做滚动数组。核心观察是第i天的状态只依赖第i-1天和更早的天数无关。因此我可以把天数这个维度整个去掉只保留dp[k][0]和dp[k][1]两份状态在循环里反复更新。不过这里有个陷阱不能简单地按照二维数组的更新顺序去覆盖否则会用上“今天刚更新过”的状态导致在一天之内完成多笔交易——这显然是错的。正确做法是k从大到小逆序更新或者把买入和卖出拆成两次遍历保证每个状态只用前一天的数据更新。4.2 基于k逆序的滚动数组实现public int maxProfitRolling(int[] prices) { int n prices.length; if (n 0) { return 0; } int K 3; int[] dp0 new int[K 1]; // 空仓状态 int[] dp1 new int[K 1]; // 持仓状态 // 初始化任何k次交易之前都不可能持仓 Arrays.fill(dp1, Integer.MIN_VALUE / 2); dp0[0] 0; for (int price : prices) { // 必须从大到小遍历k否则同一天内会重复交易 for (int k K; k 1; k--) { dp0[k] Math.max(dp0[k], dp1[k - 1] price); dp1[k] Math.max(dp1[k], dp0[k - 1] - price); } } return dp0[K]; }这段代码的更新顺序里dp0[k]和dp1[k]在同一轮k里都会更新但因为k是倒序的所以dp0[k-1]和dp1[k-1]在本轮尚未被覆盖仍然保留第i-1天的旧值。这样买入和卖出在同一天不会互相串联。很多人第一次写滚动优化时会顺手把k写成从小到大结果得到另一个完全不同的问题——在同一天内反复低买高卖收益虚高。这个坑我踩过也带过几个实习生踩过所以特别提醒一句。不过要注意这个滚动版有个小小的语义变化dp1[k] max(dp1[k], dp0[k - 1] - price)里的dp0[k-1]在k倒序时是旧值但如果我把两个更新语句换成先更新dp1再更新dp0或者用临时变量保存旧值结果会有微妙差异。原因是做卖出更新时dp0[k]可能已经被当天买入路径更新即便k倒序dp0[k]不是k-1也可能变化。所以稳妥的方案是固定先写dp0再写dp1顺序不要随意调换。我用上面的顺序实测多组随机数据结果和三维版本完全一致。4.3 更贴近业务的一种压缩基于“买卖动作”的4状态除了二维滚动数组还有一种很常见的写法是定义四个变量buy1, sell1, buy2, sell2, buy3, sell3直接模拟三次交易的顺序。本质上这是把“状态机”显式铺开。代码长一些但跑起来很快而且不容易搞错k维度。下面给一个参考public int maxProfitFourVar(int[] prices) { int buy1 Integer.MIN_VALUE / 2; int buy2 Integer.MIN_VALUE / 2; int buy3 Integer.MIN_VALUE / 2; int sell1 0, sell2 0, sell3 0; for (int price : prices) { buy1 Math.max(buy1, -price); sell1 Math.max(sell1, buy1 price); buy2 Math.max(buy2, sell1 - price); sell2 Math.max(sell2, buy2 price); buy3 Math.max(buy3, sell2 - price); sell3 Math.max(sell3, buy3 price); } return sell3; }这种写法特别适合在面试中手写因为它把“第几次交易”直接写进了变量名语义一目了然。从递推角度看sell1 - price表示用第一次卖出获得的钱作为第二次买入的购买力余额这和三维DP里的dp0[k-1] - price完全对应。唯一的风险是初值设置最好也用MIN_VALUE/2而不是Integer.MIN_VALUE否则遇到极端大价格会溢出。4.4 滚动数组和四变量的实测对比我拿长度2000的随机价格序列价格范围1到1000分别跑三维版和滚动版输出结果完全一致。性能上滚动版明显更快因为内存访问更少但三维版的优势在于调试方便可以随时打印dp[i][k][hold]矩阵定位问题非常直观。如果是做题建议先用三维版把思路跑通再改滚动版如果是在IDE里练习可以两块代码都保留做交叉验证。5. 常见坑位与调试思路从错乱的下标到离谱的收益5.1 坑位一交易次数定义不一致导致卖出后k没加这个问题在面试里非常高频。如果把“正在进行的交易”和“已完成的交易”混在一起很自然会写出dp[i][k][1] max(dp[i-1][k][1], dp[i-1][k][0] - price)来买第k次然后卖出时又写成dp[i][k1][0] max(...)结果k1会越界或者导致同一个价格被卖出两次。解决思路很简单统一用一个维度表示“已完成交易笔数”买入不改变它卖出才加1。如果不确定自己写的是哪种可以直接打印跑完后的dp数组看某一列是否单调递增。5.2 坑位二用Integer.MIN_VALUE当无效态前面提到过溢出问题。实际写过代码的人都懂Integer.MIN_VALUE - 任意正数会溢出成正数在max运算里反而变成最优解直接导致收益爆炸。比如价格正好是50000某个无效态是Integer.MIN_VALUE减去50000之后变成2147443647后面所有比较都失效。所以我强烈建议所有负无穷都写成Integer.MIN_VALUE / 2或者用一个足够小的常量如-0x3f3f3f3f约为-10^9。这个习惯不仅在股票DP里适用所有背包、路径、状态压缩DP都一样。5.3 坑位三滚动数组顺序写反同一天多次交易这是滚动优化的经典问题。如果你在每个价格上用k正序更新比如for (int k 1; k K; k) { dp0[k] Math.max(dp0[k], dp1[k - 1] price); dp1[k] Math.max(dp1[k], dp0[k - 1] - price); }那么dp1[k]在更新时读到的dp0[k-1]可能已经是当天更新过的新值意味着在同一天里先卖后买形成一秒内的循环交易。由于题目规则同一天既不能买也不能卖这种收益在逻辑上非法。验证方法构造一个严格递增、且每天涨幅很大的序列跑正序版本会发现收益等于每天涨幅的累加而不是持有到最后的收益倒序版本则输出正确结果。5.4 调试三板斧打印矩阵、造小样本、对照暴力枚举遇到DP结果不对我最常用的手段有三板斧。第一打印整个dp数组三维版逐行检查从第1天到第n天空仓收益是否逐步爬升如果某一天突然跳出一个离谱的大数马上定位到那条转移路径。第二写一个暴力枚举版本对n10的随机序列穷举所有可能的买卖组合作为ground truth。不要觉得暴力方案太笨它在验证DP正确性时是银弹。第三构造边界用例空数组、单日数组、全降序数组、价格全部相同的数组。这些用例往往能逼出初始化或循环边界的问题。下面是我常用的一小段暴力验证代码仅用于调试验证public int bruteForce(int[] prices) { int n prices.length; int best 0; // 遍历三次交易的买入、卖出下标允许空操作 for (int b1 0; b1 n; b1) { for (int s1 b1 1; s1 n; s1) { int profit1 prices[s1] - prices[b1]; for (int b2 s1 1; b2 n; b2) { for (int s2 b2 1; s2 n; s2) { int profit2 profit1 prices[s2] - prices[b2]; for (int b3 s2 1; b3 n; b3) { for (int s3 b3 1; s3 n; s3) { best Math.max(best, profit2 prices[s3] - prices[b3]); } } // 只做两次交易的情况 best Math.max(best, profit2); } } // 只做一次交易的情况 best Math.max(best, profit1); } } return best; }注意这个暴力版包含“不做交易”的情况。把所有DP版本和暴力版对比只要在n8~10的随机数据上跑几百组一致正确性基本就稳了。5.5 和“最多K次交易”模板的关系一旦把THREE的三维版本看懂改造成任意K次的方法就是一行替换把K3换成Kk。但要注意几个隐性变化如果K大于n/2任何交易机会都能抓到最优解相当于把所有“上升沿”的利润累加没必要动态规划这时可以直接走贪心求所有正差之和。这个剪枝在面试里经常被追问属于可复用的加分项。我当时整理了一个通用模板遇到这类题直接套用唯一的变动就是初始化与K的边界条件。6. 价值最大化之外从THREE到无限次、冷却期、手续费6.1 无限次交易把状态机压到两队值当交易次数无限时k维度就消失了。hold变成bool或者int转移方程变成dp0 max(dp0, dp1 price)卖出dp1 max(dp1, dp0 - price)买入这其实就是“最多一次”版本的二维状态机扩到无限次后的结果。运行逻辑仍然要谨慎用两个变量做原地更新时顺序依然有讲究老生常谈不能在同一天卖出又买入。如果题目允许同一天卖出再买入实际上等于没持有间隔那正序也是对的但绝大多数标准题目默认同一天不能同时进行两笔操作所以还是建议保留旧值的写法。6.2 冷却期和手续费在递推里加一个“锁定期”状态冷却期题目卖出后第二天不能买入要求额外加一个状态比如rest表示“今天卖出后必须休息”。状态变为三个空仓可买、持仓、冷却中。递推时持仓状态可以等也可以今天卖出进入冷却冷却状态明天转入空仓可买状态。实现上可以在dp数组里加一维或者用四个变量核心仍然是状态机思想。手续费版本更简单在卖出时减掉手续费或者在买入时加上手续费即可。很多人会纠结手续费加在哪一端我倾向于从买入端加因为这样卖出收益表达式仍然是dp1 price - fee语义更对称。6.3 序列数据规模的实战影响不要觉得O(nK)和O(n)差异只在竞赛里才重要。我在处理一段长达几十万点的金融测试序列时三维数组即使内存足够垃圾回收压力也会把计算拖得很明显。滚动数组从约600万维降到10来个变量速度提升肉眼可见。所以从这个标题延伸出的模板能优化就优化能通用就通用。6.4 扩展成一个通用的DP工具方法如果要把这段逻辑沉淀成可复用的工具我建议封装成一个方法输入价格数组和最大交易次数K输出最大收益public int maxProfitWithK(int[] prices, int K) { if (prices null || prices.length 2) { return 0; } // 如果K超过可交易次数上限退化为全部上升沿之和 if (K prices.length / 2) { int res 0; for (int i 1; i prices.length; i) { if (prices[i] prices[i - 1]) { res prices[i] - prices[i - 1]; } } return res; } int[] dp0 new int[K 1]; int[] dp1 new int[K 1]; Arrays.fill(dp1, Integer.MIN_VALUE / 2); dp0[0] 0; for (int price : prices) { for (int k 1; k K; k) { dp0[k] Math.max(dp0[k], dp1[k - 1] price); dp1[k] Math.max(dp1[k], dp0[k - 1] - price); } } return dp0[K]; }这里面的K prices.length / 2是一个关键剪枝。为什么是除以2因为一次完整的买卖至少需要两天买入一天、卖出一天序列长度为n时最多完成floor(n/2)次交易。超过这个上限约束形同虚设直接累加所有正向差值即可。这个技巧同样适用于LeetCode系列变体属于性价比极高的预判。整篇文章聊下来核心还是那句话拿到任何有限次股票交易题先问自己三个问题——底层的状态是哪些每个状态的合法转移路径是什么无效状态怎么初始化把这三个问题回答清楚无论K3还是K100都能在几分钟内写出可靠代码。我个人在实际操作中的体会是DP代码本身就这么十来行真正拉开水平差距的往往是你对状态语义的把握深度和对边界条件的敏感度。写这篇记录时我又重新跑了一遍所有版本终版虽然只有几十行但每一行背后都是踩过坑之后的取舍。如果你正在调这段代码建议把那几个常见坑逐一对照检查多半能一次跑通。