leetcode3699 锯齿过山车：从暴力O(nk²)到原地滚动的三轮进化

🎮锯齿过山车：从暴力O(nk²)到原地滚动的三轮进化

烈日当空，连村里那只掉毛信鸽都热得趴在窗台上，仿佛随时会触发什么 HeatStrokeException。我正把头伸进锅炉房里仅存的阴凉角落，院门又被“砰”地一脚踹开了。

“小白！游乐园那边来大工程了！” 村长一个滑铲冲进了屋。他满头大汗，手里举着一张画得歪歪扭扭的过山车设计图，上面密密麻麻的折线，看起来就像是我昨晚熬夜打排位时的心电图。

“游乐园？”我转过身，警惕地看着他，“就是之前一位老爷子被‘递归过山车’甩上天，然后一直在天上 return 不下来，最后触发Stack Overflow的那个游乐园？”

“哎呀，那是老黄历了！现在的游乐园可是正经项目！”村长把那张“心电图”拍在我的桌上，“新项目——锯齿过山车！要求轨道必须起伏跌宕！任意两个相邻节点高度不能相同，任意三个连续节点不能一路向上或一路向下！现在需要算出所有可能的轨道设计方案！”

我瞥了一眼他塞过来的需求文档：

锯齿过山车设计规范：
轨道由 n 个点组成，每个点的高度在 [l, r] 范围内
相邻两个点的高度不能相同（不然车会卡住）
任意连续三个点不能严格递增或严格递减（不然乘客会被甩飞）
求满足条件的轨道设计方案总数，对 10^9+7 取模
//////////////////////////////////////////////////\

村长一边擦汗，一边压低声音补充道：“n 最大 2000，高度范围也是 2000。如果今天能解决，奖金分你一半！”

一听“奖金”两个字，我原本因为高温而处于低功耗模式的大脑瞬间超频。我一拍胸脯，豪气干云，“不就是个计数问题吗？动态规划一把梭！"

状态机 DP——处理相邻约束的神器

既然牛皮已经吹出去了，接下来就是正经的思路分析时间。

先分析‘锯齿形’的本质。我盯着过山车轨道的示意图，三个节点的关系，其实只由前两个节点的大小关系和当前节点的值决定。具体来说，就像过山车的方向变化：

如果前两个节点是递增（轨道在上升 /），那当前节点必须比前一个节点小（轨道开始下降\），形成‘增-减’锯齿（/\）。
如果前两个节点是递减（轨道在下降\），那当前节点必须比前一个节点大（轨道开始上升/），形成‘减-增’锯齿（/）。

也就是说，DP 的状态需要记录两个信息：

当前节点的值是多少（记作 j）
前两个节点的关系是递增还是递减（记作 0 表示递减，1 表示递增）

所以，状态设计很清晰：

dp[j][0]：表示当前轨道节点高度为 j，且前两个节点是递减关系的方案数。 dp[j][1]：表示当前轨道节点高度为 j，且前两个节点是递增关系的方案数。

至于状态转移，其实就是模拟轨道的走向：

当要计算新的 dp[j][1]（递增状态）时，意味着前一个状态必须是递减的，且前一个位置的值要小于 j： => dp[j] [1] = 所有 dp[k] [0] 的和，其中 k < j
当要计算新的 dp[j][0]（递减状态）时，意味着前一个状态必须是递增的，且前一个位置的值要大于 j： => dp[j] [0] = 所有 dp[k] [1] 的和，其中 k > j

初始条件也很简单：

对于第一个节点，它可以是 [l, r] 范围内的任意值，而且没有"前两个节点的关系"这个概念（毕竟只有一个点，谈不上增减）。所以可以认为第一个节点的所有取值都是合法的，方案数各为 1。

想清楚这些，我突然意识到——这不就是经典的状态机 DP 吗？用状态记录局部信息（这里是增减关系），用转移保证全局约束（不能有连续三个递增或递减）。就像玩游戏时的存档读档，每个状态都是一个存档点，转移方程就是游戏规则。

我兴奋地跳了起来：二维 DP ！状态数 O(n×k)，每次转移 O(k)，总复杂度 O(n×k²)！等等，n和k都是2000——”

“等等——”，我掰着手指头算了一下，脸上的笑容逐渐凝固。8e9次运算。八十亿。就算我的CPU是液氮冷却的超算，这运算量一上，估计我也得跟那位递归过山车上的老爷子一样——迟迟return回不来。

我咽了口唾沫，深吸了口气——不管了，先跑个逻辑验证再说！

暴力DP——躲不开TLE的阴影

我噼里啪啦敲下暴力 DP，忐忑地点下了“Submit”：

MOD = 10**9 + 7 
k = r - l + 1  # 高度范围的长度

# dp[j][0/1]: 最后一个节点值是 j+l，0表示递减，1表示递增
dp = [[0, 0] for _ in range(k)]

# 初始化：第一个节点可以是任意值
for j in range(k):
    dp[j][0] = 1
    dp[j][1] = 1

# 从第二个节点开始迭代 DP
for i in range(2, n + 1):
	new_dp = [[0, 0] for _ in range(k)]  # 创建新的 DP 数组，用于存储当前状态

	for j in range(k):  # 当前节点可填的值（高度范围内）
		# 计算 new_dp[j][1]：递增状态，前一个状态必须是递减，且值 < j
		for prev in range(j): 
            new_dp[j][1] = (new_dp[j][1] + dp[prev][0]) % MOD
		
        # 计算 new_dp[j][0]：递减状态，前一个状态必须是递增，且值 > j
        for prev in range(j + 1, k): 
            new_dp[j][0] = (new_dp[j][0] + dp[prev][1]) % MOD

	dp = new_dp  # 用新层的状态替换旧层

# 最后一层DP完成后，统计所有可能的方案数
ans = 0
for j in range(k):
	ans = (ans + dp[j][0] + dp[j][1]) % MOD

return ans

提交——红色TLE如期而至——八十亿次循环，Python跑完的时间够我把泡面从红烧牛肉味吃到全系列绝版。

我盯着屏幕上那个红叉，陷入了沉思：“所以……我的状态转移是对的，只是姿势不对？”

前缀和优化——区间求和必杀技

“你的内层循环在干什么？” 老勇者不知道什么时候出现在我身后，手上还拿着两瓶冰可乐。

我像是看到了救星：“大佬！快救救孩子！” 老勇者递给我一瓶可乐，指了指我的代码：

“你看，你的转移方程是这样的：

new_dp[j][1] = sum(dp[k][0])，其中 k < j
new_dp[j][0] = sum(dp[k][1])，其中 k > j

这是什么——典型的区间求和问题！你在内层循环里每次都重新遍历累加，当然慢。如果能在 O(1) 时间内得到任意区间的和，是不是就能把内层循环砍掉？”

我眼睛一亮，脑海中仿佛有一道闪电劈过，照亮了我那被 TLE 阴影笼罩的大脑：“您的意思是……前缀和？！”

“一点就通。”老勇者满意地点点头，“前缀和的核心思想是预处理+查表。具体到你的问题，就是把‘小于 j 的递减状态之和’ prefix[j] ，和用于计算 ‘大于 j 的递增状态之和’ prefix[k]、prefix[j+1] 提前算好，O(1) 直接拿。这样内层循环就从 O(k) 降到了 O(1)，总复杂度从 O(n×k²) 降到了 O(n×k)。”

我恍然大悟，猛地一拍大腿：“对！用 accumulate 快速计算前缀和，把转移变成 O(1)！这像把每次都要现算的账本，提前做成了汇总表，查账的时候直接翻对应页就行！"

老勇者点了点头，又补了一刀：“还有，你那个二维数组是不觉得碍眼吗？”

“你仔细看，“老勇者指了指代码，“你的 dp 数组在每一轮迭代时，只依赖于上一层的状态，两层之间互不干扰。但你每轮都新建一个 new_dp，内存不要钱啊？而且频繁创建新对象还会触发 GC，进一步拖慢速度。”

“你有没有想过，”他顿了顿，“用两个一维数组 f0 和 f1 交替更新就行了。”

“f0[j] 表示最后一个节点值是 j 且前两个节点递增的方案数，f1[j] 表示最后一个节点值是 j 且前两个节点递减的方案数。每轮迭代先算出两个前缀和数组 s0 和 s1，然后遍历每个高度 j，直接用前缀和更新 f0[j] 和 f1[j]。”

我盯着他，脑子里像是有无数个齿轮在飞速转动，然后"咔哒"一声，全部咬合到位——“就像玩 RPG 游戏，前缀和是直接用传送卷轴到指定等级，原地优化是连背包都不用整理，直接把装备换成新的！”

MOD = 10 ** 9 + 7
k = r - l + 1

f0 = [1] * k
f1 = [1] * k

# 从第二个位置开始迭代
for _ in range(n - 1):
    s0 = list(accumulate(f0, initial=0))
    s1 = list(accumulate(f1, initial=0))
    for j in range(k):
        f0[j] = s1[j] % MOD
        f1[j] = (s0[k] - s0[j + 1]) % MOD

return (sum(f0) + sum(f1)) % MOD

提交，AC 瞬弹。绿色的勾号亮起的瞬间，我差点从椅子上蹦起来。我刚准备截屏纪念下，老勇者突然伸手按住了我的键盘。

原地滚动——状态复用的巅峰

“等等，”他眯起眼睛，“你那个s0和s1数组，是真的需要单独存起来吗？”

我愣住了：“什么意思？不存前缀和数组……我怎么查表？s1[j]是f1的前缀和，s0[k] - s0[j+1]是f0的后缀和，没有这两个数组，难道每次都重新算一遍？”

“你仔细看。”老勇者指着代码里的循环，“f1[j] 需要的是 s1[j]——也就是 f1 中所有下标小于 j 的值的和。f0[j] 需要的是 s0[k] - s0[j+1]——也就是 f0 中所有下标大于 j 的值的和。这两个东西，一定要提前把整个前缀和数组全算出来才能拿吗？”

“前缀和是顺着走，后缀和是逆着走。”他在纸上画了一行从左到右的箭头，又在上面画了一行从右到左的箭头，“你完全可以在更新状态的同时，用一个变量维护当前累加值——顺着走的时候，每走一步就把当前值加入累加器，下一步的转移直接取这个累加器。逆着走同理，只是方向反过来。”

老勇者嘴角勾起一丝神秘的微笑，像是在玩一个高深的文字游戏：”原地滚动——前缀和和后缀和的计算就和状态更新融为一体，空间压到O(1)，时间还是O(nk)，常数还更小。”

“……您的意思是，在更新 f0[j] 和 f1[j] 的同时，用一个变量 pre 来实时维护前缀和？”我试图厘清头绪，感觉大脑CPU要干烧了。

老勇者看我这副快要宕机的样子，叹了口气，敲了段示意代码：

# 计算 f1[j]：依赖所有 f0[k] (k < j) 的和
pre = 0 
for j in range(k): 
    f1[j] = pre    # pre 就是 sum(f0[0], f0[1], ..., f0[j-1]) 
    pre += f0[j]   # 把当前的 f0[j] 加入前缀和，为下一个 j 做准备

“看到没？” 老勇者指了指代码，“f1[j] 依赖于 f0 的前缀和，也就是所有下标小于 j 的 f0 之和。从左到右顺着遍历，用一个变量 pre 一路累加 f0 的值。走到 j 的时候，pre 恰好就是 f0[0] 到 f0[j-1] 的累加和——直接赋值给 f1[j]，然后顺手把当前 f0[j] 加进 pre 里，为下一个位置做准备。”

“不要额外开 s0 数组的空间，一轮 O(k) 遍历就能同时完成前缀和的计算和状态的更新。这就是原地计算前缀和的精髓——边算边用，用完即弃。”

我琢磨了一会，恍然大悟：“那对于 f0[j]（递减状态），我需要的是所有大于 j 的 f1[k] 之和，也就是后缀和。我可以从右到左遍历，用同样的方法维护一个 suf 变量！”

“总算通了。”老勇者满意地笑了，“一趟顺着走更新 f1，一趟逆着走更新 f0。两趟遍历，两个变量，前缀和和后缀和就地计算，算完即用，用完即弃。根本不用调 accumulate ！”

他顿了顿，补充道：“还有最后一个细节——你有没有发现，每一轮迭代结束后，f0 和 f1 的角色其实互换了？”

我仔细想了想，瞬时明白了：“对啊！因为下一轮的‘递增状态’依赖于上一轮的‘递减状态’，反之亦然。所以我可以在计算完后，直接交换 f0 和 f1 的引用，这样下一轮迭代时，原来的 f1 就变成了新的 f0，原来的 f0 变成了新的 f1。这样我就不需要额外的变量来存储新状态，直接在原数组上修改就行！”

老勇者眼中闪过一丝赞赏：“没错。这就是滚动数组的思想。把两轮之间的状态复用做到了极致——不仅省空间，还避免了频繁创建新对象的开销。”

MOD = 1_000_000_007 
k = r - l + 1

f0 = [1] * k 
f1 = [1] * k

# 从第二个位置开始迭代
for _ in range(n - 1):
    # 从左到右遍历，用 pre变量维护前缀和，同时更新 f1[i]
    pre = 0
    for i, v in enumerate(f1):
        f1[i] = pre % MOD  # 先赋值再累加，保证 f1[i] 得到的是 f0[0] 到 f0[i-1] 的和
        pre += v

	# 从右到左遍历，用 suf变量维护后缀和，同时更新 f0[i]
	suf = 0
	for i in range(k - 1, -1, -1):
        v = f0[i]
        f0[i] = suf % MOD  # 同样先赋值再累加，保证 f0[i] 得到的是 f1[i+1] 到 f1[k-1] 的和
        suf += v

	# 交换 f0 和 f1，为下一轮迭代做准备
	f0, f1 = f1, f0

# 统计所有可能的最后一个元素的方案数
return (sum(f0) + sum(f1)) % MOD

我看着这段代码，感觉它就像一件艺术品——简洁、优雅、高效。没有多余的数组，没有嵌套的循环，只有两个一维数组和三个变量，就完成了整个 DP 的计算。

“这才是真正的原地算法。”老勇者拿起桌上那瓶快乐水，畅快地灌了一大口，“时间复杂度 O(n×k)，空间复杂度 O(k)，而且常数因子极小。Python 跑四百万次运算，也就是一眨眼的功夫。”

“大佬，”我深吸一口气，双手抱拳，“您这点拨简直是把我的脑子从单核直接超频到了多核啊！”

老勇者微微一笑，放下快乐水，语气变得语重心长：“记住，优化的本质不是炫技，而是找到问题的结构和规律。”

他伸出三根手指，像是在数技能冷却时间：

“第一，前缀和之所以能用，是因为你的转移方程涉及区间求和——这是问题的数学结构。
第二，原地计算之所以可行，是因为你的遍历顺序和前缀和的累积方向一致——这是算法的执行顺序。
第三，滚动数组之所以有效，是因为你的状态只依赖于上一层——这是 DP 的状态依赖关系。

这些技巧都不是孤立的魔法，而是建立在对问题深刻理解基础上的组合拳。就像打游戏时的连招，不是死记硬背按键顺序，而是知道每个技能的冷却时间、攻击范围和衔接时机。”

他站起身，拍了拍我的肩膀，力道不轻不重：“算法也是一样，懂原理，才能玩出花。你今天的表现不错——至少没在我说完’前缀和’之后问我’那是啥’。”

我挠了挠头，有点不好意思：“那不是因为有您在嘛……”

老勇者哼了一声，算是接受了我的马屁：“前缀和是优化 DP 的常规武器，今天你算是正式入门了。”

他把可乐往口袋一揣，转身向门口走去。快走到门边时，突然停下脚步，回头补了句：“如果下次 n 飙到 10^6，前缀和也不够用，那就得上矩阵快速幂了。不过那是另一个副本的事了。”

我站在原地，脑子里回荡着"矩阵快速幂"“另一个副本"这些词——矩阵快速幂？今天的脑容量都快被锯齿形数组撑爆了好吧！

尾声

窗外那只掉毛信鸽被热得翅膀都懒得扇，蹲在窗台上歪头看我，眼神里写满了“你这题优化得比我的羽毛还顺”。

从开二维DP到前缀和优化，从前缀和数组到原地滚动——同一道题，三轮迭代，每一次都在追问同一个问题：这个中间结果真的需要存吗？能现场算的，就别存；能用变量滚动的，就别开数组。

望着老勇者离去的背影，我默默在魔法书上写下今天的总结：

以后遇到类似的 DP 问题，记得多问自己几个问题：
转移方程能不能简化？（有没有重复计算可以消除？）
空间能不能进一步优化？（能不能原地计算？能不能滚动数组？）
状态定义能不能更精简？（有没有冗余信息可以砍掉？）

写完，我合上魔法书，长舒一口气。今天的收获，够我消化好一会了。

又道是：

锯齿轨道zig又zag，暴力炸出 TLE。
前缀和表砍循环，原地滚动省空间。 **大佬指点迷津处，矩阵快速幂再见。 **

本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。