🎮 游乐园峰谷过山车：数位DP的修行

第一章：村长的新任务

“小白！别睡了！有新任务了！” 村长一脚踹开我家大门，手里挥舞着一份皱巴巴的羊皮卷轴。我一个激灵从床上弹起来，下意识就去摸魔法书——这开场白我太熟了，每次村长用这个句式，后面铁定跟着一道新题。

“还记得算法乐园那个没设 base case 的‘递归过山车’吗？”他把卷轴拍在我桌上，“乐园那边连夜开了事故复盘会，紧急关停了项目，总算把老爷爷从轨道上救下来了。他们痛定思痛，在旁边新建了个项目，叫‘数位过山车’。”

我拿起卷轴，村长继续解释：“ 这次项目上线前要做安全评估，再不敢直接莽了。新过山车的轨道由数字构成——每个数字就是一段铁轨，每一位是铁轨上的一个连接点。如果某一段连接点比两边都高，就是‘峰’；比两边都低，就是‘谷’。峰和谷太多意味着轨道起伏太剧烈，车开上去乘客容易被动升天，重蹈爷爷的覆辙。所以他们需要计算**‘波动值’**——也就是峰和谷的总数——来评估轨道安全性，决定安全带是用两根还是五根。”

我瞅了眼卷轴，上面写着波动值的定义：

峰：某一位数字严格大于左右两边——像山峰一样凸起来，在上面一览众山小。 谷：某一位数字严格小于左右两边——像山谷一样凹下去，在里头抬头望星空。 首尾两位不能算峰或谷——边界保护，毕竟第一个和最后一个连邻居都凑不齐。 少于3位的数字波动值为0——太短了没法波动

“你的任务，” 村长用指关节敲了敲卷轴，“是计算区间 [num1, num2] 内所有数字的波动值之和。乐园那边要拿着这个数据去申请保险。”

我盯着卷轴看了三秒，突然笑出声：“这不就是遍历每个数字，拿字符串滑窗检查一下峰和谷嘛。zip(s, s[1:], s[2:]) 三连滑窗，峰谷一眼扫完，比在游戏里开扫描模式还快。村长你是不是又在放水？”

村长冷笑一声。那种笑容我见过——上次他给我推游乐园正式服 5×10⁴ 数据的时候，也是这副表情，像一个提前看过剧透的副本 Boss。“数据范围 num2 ≤ 10⁵，暴力当然能过。但我先给你打个预防针——说不定哪天范围就扩到 10¹⁸ 了呢？”

说完，村长便甩袖而去。我透过窗户望了一眼算法乐园的方向，那座“数位过山车”的轨道已经在晨光中闪闪发亮——10⁵ 嘛，先暴力 AC 了再说。至于 10¹⁸……到时候再想呗，未来的我肯定有办法。实在不行，不还有老勇者嘛。

第二章：暴力枚举——三连 zip 横扫千军

直接暴力：从 num1 一路遍历到 num2，每个数字转成字符串，然后掏出 Python 的 zip(s, s[1:], s[2:]) 三连滑窗，把连续三位 a、b、c 一次性拎出来。如果 a > b < c，说明 b 是个谷，轨道在这里砸了一个坑；如果 a < b > c，说明 b 是个峰，轨道在这里顶出一个包。每发现一个峰或谷，计数器加一。遍历完所有数字，返回总数完事。

def totalWaviness(num1: int, num2: int) -> int:
    res = 0
    for i in range(num1, num2 + 1):  # 遍历区间内每个数字
		s = str(i)  # 转成字符串方便逐位访问
        for a, b, c in zip(s, s[1:], s[2:]):  # 滑动窗口取连续三位
            if a > b < c:  # 谷
                res += 1
            elif a < b > c:  # 峰
                res += 1
	return res

写完一跑，秒出AC。zip(s, s[1:], s[2:]) 这个三连滑窗真是比德芙还丝滑——s 是原字符串，s[1:] 是从第二位开始的字符串，s[2:] 是从第三位开始的字符串，三个错位排列的字符串往 zip 里一塞，直接吐出所有连续三位的组合。时间复杂度 O(N·L)，N 是区间长度，L 是数字平均位数。10⁵ 个数字，每个最多六七位，总操作量撑死几十万次。

第三章：小白的 数位DP 困境

提交完暴力代码，我靠在椅背上准备摸鱼，脑子里却自动回放起村长临走时的那个冷笑——“如果哪天范围扩到 10¹⁸……”，我越想越不是滋味。村长的嘴，骗人的鬼，但村长的预言，比 stack trace 还准。上次他说“以后会有大数据版本”，隔天正式服就砸脸上了。这次他特意打个预防针，八成是在给我提前剧透。

10¹⁸ 意味着什么？意味着如果我还用暴力遍历，评测机怕是要甩我个TLE。我必须想一个不依赖区间长度的解法。

我在魔法书里翻来翻去，目光落在一页标注着“数位 DP”的章节上。那是老勇者上次去邻村之前塞给我的，说是“有空看看，以后用得上”。我当时翻了前两页，看到满眼的 dfs(i, is_limit, is_num) 就觉得脑壳疼，随手一合当枕头用了。现在想想，真是书到用时方恨少，码到跑时方觉糙。

“数位 DP……”我喃喃自语，“ 核心思想应该是按位搜索——把数字一位一位填出来，在填的过程中统计波动值。这样就不用枚举每一个完整的数字，而是枚举每一位可能的取值。相当于把十亿个数字压缩成几十个状态，用记忆化搜索代替暴力遍历。”

思路大概是——从最高位开始，逐位尝试 0 到 9——每填一个新的数字 d，我需要知道它和前一位 last_digit 的关系——变大了、变小了，还是持平。但峰和谷的判断需要三位数字。要判断前一位是不是峰，我得同时知道前一位的数字、更前一位的数字、以及当前位 d。也就是说，当我填下 d 的时候，才能回头判定前一位是不是峰或谷。“那我该记录什么状态？”我拿笔在草稿纸上乱画。

首先肯定要有 i，表示当前填到第几位，这是数位 DP 的标配，用来判断递归什么时候到头。然后得有 last_digit，记录上一位填的是什么数字，不然没法算当前位是升还是降。还得搞个 last_cmp，记录上一位和更前一位的比较趋势——上升记 1，下降记 -1，持平记 0。这样当上一位与当前位的新趋势 c 算出来之后，如果 c * last_cmp < 0，就说明趋势反转了，前一位要么是峰要么是谷，波动值加一。

“等等，” 我咬着笔杆皱起眉头，“还有上下界的问题。我只能在 num1 到 num2 之间搜，不能搜出范围外。需要 limit_low 和 limit_high 两个布尔值，分别标记当前是否要受下界和上界的约束。另外，如果 num1 和 num2 位数不同，比如num1=1，num2=100，数位对齐后数字 5 实际上是 ‘005’，前两个零不能参与峰谷判断，得想办法标记前面是否已经填过非零数字，没开始之前趋势 c 直接设成 0。”

我盯着纸上列出的状态参数——i、last_cmp、last_digit、limit_low、limit_high——光参数就已经五个了，还没算上前导零的判断。但更让我卡住的还不是参数多，而是另一个根本性的问题。

“返回值怎么设计？” 这是我最困惑的地方。之前学数位 DP 的时候，最常见的套路是“统计满足条件的数字个数”——dfs 返回从当前状态开始能构造出多少个合法数字，最后调用 dfs(0, true, true) 就是答案。还有一种是“统计权值和”——比如求所有数字的数位和之和，返回值是从当前状态开始所有数字的某个属性累加值。

但这道题既不是数个数，也不是简单的权值和。我要的是“波动值之和”——先算每个数字的波动值，再把所有数字的波动值加起来。波动值本身是一个数字内部峰和谷的计数，它在填数字的过程中动态累加，不是一个静态的属性。那么问题来了，我到底应该把波动值当成状态参数 waviness 一路传下去，到了底层直接返回？还是应该把它当成返回值的一部分，让每层递归把后续所有数字的波动值之和汇总上来？

我越想越乱，草稿纸上画满了状态转移图，又全划掉了。我盯着天花板上被锅炉熏出的水渍，第一次觉得数位 DP 比递归过山车还难。递归过山车好歹只有一个问题——没设 base case；而数位 DP 有一百个问题，每一个都在问我：“你这个状态设计对了吗？”参数怎么分、返回值怎么定、记忆化怎么开、前导零怎么处理，全搅在一起，像极了一个没有封装的单体应用——牵一发而动全身。

正在我纠结要不要干脆放弃治疗、等正式服上线再说的时候，门口传来一阵慢悠悠的脚步声，伴随着打火机点烟斗的“咔嗒”声——老勇者从邻村回来了。

“怎么，数位 DP 把你难住了？”他倚在门框上，慢悠悠地吐出一口烟圈。

第四章：老勇者的 数位 DP 锦囊

老勇者没急着进屋，先在门口磕了磕烟斗里的灰，然后慢悠悠地踱到我桌前，低头扫了一眼我那画满又划掉的草稿纸。他看了足足五秒钟，表情就像在 code review 里看到了一坨没有注释的祖传代码。

“状态设计全写在纸上了，但你没把它们分清楚。”他把烟斗往桌角一敲，指着纸上那几个被我圈了又圈的参数，“数位 DP 的参数分两类——一类叫‘限制状态’，管的是‘你能填什么’；一类叫‘计算状态’，管的是‘你填完之后发生了什么’。你把它们全搅在一起，自然觉得脑子里的栈要溢出了。”

他在纸上画了一道线，左边写“限制”，右边写“计算”：

“限制状态有两个：limit_low 和 limit_high。它们只做一件事——卡死当前位能填的数字范围。如果 limit_high 为 true，说明前面每一位都死死贴着上界，当前位绝对不能超过 high_s[i]；一旦某一位填了一个比上界小的数字，后面的 limit_high 就永久变成 false，所有位直接解放，0 到 9 随便填。limit_low 同理，只不过方向相反——一旦某一位填了一个比下界大的数字，后面就再也不用看下界的脸色了。这两个参数就是数字世界里的边界门卫。”

“计算状态也有两个：last_digit 和 last_cmp。它们只做一件事——判断峰和谷。last_digit 是上一位的数字，last_cmp 是上一位和更前一位的趋势关系，1 是上升，-1 是下降，0 是持平。当你填下当前位 d 时，先算出新的趋势—— c = (d > last_digit) - (d < last_digit)，一个表达式同时处理大于、小于、等于三种情况，然后看一眼 c * last_cmp ：峰和谷本质都是方向改变，在数学上就是乘积为负，也就是说如果< 0，说明趋势反转，上一位要么是峰要么是谷，波动值加一。这两个参数完全不关心上下界，只关心数字之间的相对大小。”

“至于前导零——用 last_cmp == 0 就能兼顾。还没填有效数字之前，趋势保持为零，c * last_cmp 永远是 0，永远不会触发峰谷判断。把前导零的三个虚拟零拆开看，它们之间全是持平，趋势变化为零，自然不会有峰谷误判。”

他在两个区域之间又画了一根线，在计算状态那边补了一个参数：“至于波动值 waviness，它既不是限制也不是计算，它是你最终要交的答案本身。这个东西的处理方式，有两种流派：一种把它当行李一路扛下去，一种把它当战报一层层报上来。看好了，我两个都写给你。”

他在纸上写下第一种写法：

low_s = list(map(int, str(num1)))
high_s = list(map(int, str(num2)))
n = len(high_s)
diff_lh = n - len(low_s)

@cache
def dfs(i, waviness, last_cmp, last_digit, limit_low, limit_high):
    if i == n:
        return waviness
    
    lo = low_s[i - diff_lh] if limit_low and i >= diff_lh else 0
    hi = high_s[i] if limit_high else 9
    
    res = 0
    is_num = not limit_low or i >= diff_lh
    for d in range(lo, hi + 1):
        c = (d > last_digit) - (d < last_digit) if is_num else 0
        w = waviness
        if c * last_cmp < 0:
            w += 1
        res += dfs(i + 1, w, c, d,
                   limit_low and d == lo,
                   limit_high and d == hi)
    return res
return dfs(0, 0, 0, 0, True, True)

“这个版本最符合直觉——波动值放在参数里，顺着递归一路带到底。每发现一个峰或谷，就 w += 1，最后叶子节点把累加好的结果交上去。就像你拎着一个行李袋，每经过一个峰或谷就往袋子里扔一颗石子，到了终点直接把袋子倒出来数。状态设计也一目了然：limit_low 和 limit_high 是门卫，卡取值范围；last_digit 和 last_cmp 是轨道设计师，管峰谷判断；waviness 是最终成绩单，一路传到底。”

“但是，”他把烟斗往桌角一敲，“这个版本藏着一个坑——@cache 会把所有参数都当成缓存 key，包括 waviness——问题来了：到达同一个 (i, last_cmp, last_digit, limit_low, limit_high) 状态时，waviness 可能完全不一样，因为 waviness 不同，缓存会直接把它们当成了两个不同的状态，各算各的。等于你给每一条搜索路径都建了一个独立的缓存项，记忆化名存实亡，退化成了带 @cache 装饰器的暴力回溯。”

我盯着代码里那个被 @cache 包裹的 dfs，参数表里 waviness 赫然在列——每次峰谷累加，它就变一次，等于每条搜索路径都有一个独一无二的缓存 key——“那怎么改？”我追问。

“把 waviness 从参数里踢出去，让它变成返回值的一部分。行李别自己扛了，让每个子树统一上报战报。”他在纸上写下第二种写法：

low_s = list(map(int, str(num1)))  
high_s = list(map(int, str(num2)))
n = len(high_s)
diff_lh = n - len(low_s)

# dfs 返回两个数：子树波动值总和，子树合法数字个数
@cache
def dfs(i, last_cmp, last_digit, limit_low, limit_high):
    if i == n:
        return 0, 1  # 能递归到终点的都是合法数字

    lo = low_s[i - diff_lh] if limit_low and i >= diff_lh else 0
    hi = high_s[i] if limit_high else 9

    waviness_sum = num_cnt = 0
    is_num = not limit_low or i > diff_lh  # 前面是否填过数字
    for d in range(lo, hi + 1):
        # 当前填的数不是最高位，c 才有意义
        c = (d > last_digit) - (d < last_digit) if is_num else 0
        sub_waviness_sum, sub_num_cnt = dfs(i + 1, c, d, 
                                            limit_low and d == lo, 
                                            limit_high and d == hi)
        waviness_sum += sub_waviness_sum  # 累加子树的波动值
        num_cnt += sub_num_cnt            # 累加子树的合法数字个数
        if c * last_cmp < 0:  # 形成了一个峰或谷
            waviness_sum += sub_num_cnt  # 这个峰谷会出现在 sub_num_cnt 个数字中
            return waviness_sum, num_cnt

return dfs(0, 0, 0, True, True)[0]

“注意看，这个版本的返回值是一个元组——(子树波动值总和, 子树合法数字个数)。每个节点不从上面接收任何波动值，只向上汇报两件事：我这棵子树里所有完整数字的波动值加起来是多少，以及我这棵子树里一共有多少个合法数字。“ 他指着核心逻辑，继续解释道：“当发现当前位形成峰或谷时——也就是 c * last_cmp < 0 时，不是 +1，而是 + sub_num_cnt——因为当前位形成的这个峰或谷，不是只影响一个数字，而是会影响从这条路走到底的每一个合法数字。相当于你这个峰或谷不能只给自己加一分，而是要给从你这儿毕业的所有合法数字各加一分。”

他顿了顿，举了个例子：“假设处理数字范围 [100, 999]，当递归到第2位时： 第一种写法：路径 1→2→? 和 1→3→? 会因为 waviness 不同而分别计算，即使它们在第2位之后的子树结构完全相同，缓存也命中不了，各算各的。 第二种解法：对于相同的 (i=2, last_cmp, last_digit, limit_low, limit_high) 状态，子树返回的 (波动值总和, 数字个数) 永远一模一样——因为波动值不再是你自己扛的行李，而是子树统一上交的战报。不管之前的历史路径是什么，只要这五个参数相同，缓存直接命中，子树不用重新算。如果当前位恰好形成了峰或谷，直接 + sub_num_cnt，把贡献批量加上去，一步到位。”

我盯着两个版本来回看了好几遍，恍然大悟：“ 所以第一种是把波动值当‘个人行李’，每个搜索路径自己拎着走，但拎的东西不一样就没法共享存储柜。第二种是把波动值当‘团队战报’，每个子树统一汇总上报，相同的搜索状态无论从哪条路进来，返回的战报完全一样，共用储物柜。波动值从‘自己扛’变成了‘向上报’，waviness 从参数里消失，@cache 缓存命中率直接拉满。”

老勇者满意地点点头，把烟斗往嘴里一叼：“ 把波动值当行李扛下去，看似符合直觉，但每个搜索路径的行李内容都不一样，相同状态永远无法共享缓存——这是典型的“有后效性”，历史路径影响了当前决策，记忆化形同虚设。而把波动值当战报报上来，让每个子树返回一个与历史无关的元组 (子树波动值总和, 子树合法数字个数)，当前位的峰谷贡献通过 + sub_num_cnt 批量结算，五个参数锁死缓存 key，无后效性完美满足——这才是 DP 该有的样子。”

他站起身朝门口走去，快到门边时回头补了一句，“数位 DP 的精髓，不是怎么搜，而是怎么设计状态和返回值，让记忆化从装饰品变成核武器。波动值是行李还是战报，决定了你的缓存命中率是趋近于零还是接近一百。”

第五章：数位 DP 复盘——从行李到战报的进化

锅炉里的火苗噼啪响了两声，像极了我脑袋开窍的声音。

回看这一整天的折腾，从暴力滑窗到数位 DP，我踩的坑差不多能写一本短篇小说，名字都想好了，叫《数位 DP 从入门到放弃再到真香》。状态列不全，不知道谁该进参数、谁该进返回值，像个出门旅行把所有家当全攥在手里却找不到行李箱的焦虑旅客，最后还被缓存命中率敲打了一番，数位 DP 的门槛从来不在“能不能搜”，而在“搜完之后能不能记住”，而能不能记住，取决于状态设计有没有做到无后效性。

我把魔法书翻到“数位 DP”那一章，把两个版本工工整整地贴上去：

3751 - 范围内总波动值 I 暴力解法：zip 三连滑窗，O(N·L)，数据 10⁵ 时秒出 数位 DP 解法：记忆化搜索，O(位数 × 状态数) 核心收获：波动值是战报，不是行李。限制状态和计算状态分开，记忆化才能真正发威。c * last_cmp < 0 一行统一峰谷判断。峰谷贡献不是 +1，是 + sub_num_cnt。

我在“波动值是战报，不是行李”下面又重重划了道下划线。靠在椅背上，我透过窗户望了一眼算法乐园的方向，天边那座数位过山车的轨道在夕阳下闪闪发亮。

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