T3753.范围内总波动值 II

数位dp, https://leetcode.cn/problems/total-waviness-of-numbers-in-range-ii/

给你两个整数 num1 和 num2，表示一个闭区间 [num1, num2]。

一个数字的 波动值 定义为该数字中峰和谷的总数：

如果一个数位 严格大于 其两个相邻数位，则该数位为峰。
如果一个数位 严格小于 其两个相邻数位，则该数位为谷。
数字的第一个和最后一个数位不能是峰或谷。
任何少于 3 位的数字，其波动值均为 0。

返回范围 [num1, num2] 内所有数字的波动值之和。

示例 1：

输入： num1 = 120, num2 = 130

输出： 3

解释：

在范围 [120, 130] 内：

120：中间数位 2 是峰，波动值 = 1。
121：中间数位 2 是峰，波动值 = 1。
130：中间数位 3 是峰，波动值 = 1。
范围内所有其他数字的波动值均为 0。

因此，总波动值为 1 + 1 + 1 = 3。

示例 2：

输入： num1 = 198, num2 = 202

输出： 3

解释：

在范围 [198, 202] 内：

198：中间数位 9 是峰，波动值 = 1。
201：中间数位 0 是谷，波动值 = 1。
202：中间数位 0 是谷，波动值 = 1。
范围内所有其他数字的波动值均为 0。

因此，总波动值为 1 + 1 + 1 = 3。

示例 3：

输入： num1 = 4848, num2 = 4848

输出： 2

解释：

数字 4848：第二个数位 8 是峰，第三个数位 4 是谷，波动值为 2。

提示：

1 <= num1 <= num2 <= 10^15

一个优雅且高效的解决方案是使用 数位 DP（Digit DP）。

解题思路

由于需要求区间 $[n u m 1, n u m 2]$ 内所有数字的波动值之和，可以将问题转化为求 $[1, n]$ 内所有数字的波动值之和，即 solve(num2) - solve(num1 - 1)。

对于给定的 $n$ ，可以通过数位 DP 来统计：

状态定义：使用深度优先搜索 dfs(i, pre2, pre, is_limit, is_num)，其中：
- i：当前正在考虑的数位下标（从 $0$ 到 $L - 1$ ）。
- pre2：当前数位的前前一个数位。如果尚未确定，则为 $- 1$ 。
- pre：当前数位的前一个数位。如果尚未确定，则为 $- 1$ 。
- is_limit：表示当前放置的数位是否受到 $n$ 的对应位限制。
- is_num：表示前面是否已经填入了有效的数字（用于处理前导零）。
返回值设计：由于需要统计总波动值，dfs 函数可以返回一个二元组 (cnt, tot)：
- cnt：在当前状态下，后续能组成合法数字的个数。
- tot：在当前状态下，所有合法数字在当前及后续数位中所贡献的总波动值。
状态转移与波动值计算：当处于第 i 位，且前面已经填入了至少两个数位（即 is_num 为真且 pre2 != -1），在尝试填入当前数位 d 时，可以检测前一个数位 pre 是否形成了一个峰或谷：
- 如果满足 pre2 < pre > d（峰）或 pre2 > pre < d（谷），则说明 pre 这一位是一个波动点。
- 此时，该过渡对后续所有组合出来的 cnt 个数字，每一个都会贡献 $1$ 点波动值。因此总波动值增加 cnt * 1。

Python 3 实现

python

from functools import cache

class Solution:
    def totalWaviness(self, num1: int, num2: int) -> int:
        
        def solve(n: int) -> int:
            if n <= 0:
                return 0
            s = str(n)
            L = len(s)
            
            @cache
            def dfs(i: int, pre2: int, pre: int, is_limit: bool, is_num: bool):
                # 如果填完了所有数位
                if i == L:
                    return (1, 0) if is_num else (0, 0)
                
                limit = int(s[i]) if is_limit else 9
                res_cnt = 0
                res_tot = 0
                
                # 情况 1：不填数字（作为前导零处理，仅在还没填过数字时允许）
                if not is_num:
                    c, t = dfs(i + 1, -1, -1, False, False)
                    res_cnt += c
                    res_tot += t
                    
                # 情况 2：填入数字 d
                low = 0 if is_num else 1
                for d in range(low, limit + 1):
                    next_limit = is_limit and (d == limit)
                    
                    # 检查 pre 是否构成峰或谷
                    contrib = 0
                    if is_num and pre2 != -1:
                        if (pre2 < pre > d) or (pre2 > pre < d):
                            contrib = 1
                    
                    c, t = dfs(i + 1, pre, d, next_limit, True)
                    res_cnt += c
                    res_tot += (t + c * contrib)
                    
                return res_cnt, res_tot

            return dfs(0, -1, -1, True, False)[1]

        return solve(num2) - solve(num1 - 1)

复杂度分析

时间复杂度：最大数字长度 $L \leq 16$ 。 DP 的状态数为 $L \times 11 \times 11 \times 2 \times 2 \approx 7744$ 个。每个状态最多转移 $10$ 次。因此，每次调用 solve 的计算量在 $10^{5}$ 级别，运行时间通常在几十毫秒内，远低于时间限制。
空间复杂度：由于使用了带备忘录的递归，空间复杂度取决于状态个数以及递归栈深度，空间复杂度为 $O (L \times 11 \times 11) \approx O (1)$ 级别，内存占用极小。

没关系，这个算法确实涉及一些动态规划的专业技巧（通常称为“数位 DP”），初看比较抽象。
我们可以用更通俗、更直观的方式来拆解这个解法。
第一步：怎样才算一个“峰”或“谷”？
要判断一个数位是不是“峰”或“谷”，我们需要看连续的 3 个数位。假设这三个连续的数位依次是：A -> B -> C。
峰：B 比两侧都大（A < B > C）
谷：B 比两侧都小（A > B < C）
因此，当我们在从左往右写一个数字的时候：
刚写下第一个数字 A，无法判断。
写下第二个数字 B，依然无法判断。
当写下第三个数字 C 的瞬间，我们立刻可以判断：刚才写的 B 是不是一个峰或谷。
这就是为什么我们的程序在写当前数字 d（即 C）的时候，需要知道前一个数字 pre（即 B）和前前一个数字 pre2（即 A）。
第二步：为什么要逐位构造数字？
因为范围最大到 $10^{15}$ ，我们不可能用 for 循环一个一个去判断每个数字。我们需要像画树状图一样，从左到右，一位一位地“拼”出所有可能的数字。
例如，我们要拼一个不超过 $120$ 的三位数：
第一位可以选：0（代表不填）、1。
如果第一位选了 1，第二位可以选 0, 1, 2。
如果前两位选了 1 和 2，第三位只能选 0（因为不能超过 $120$ ）。
这样我们就拼出了 120。
第三步：如何计算总波动值？（核心难点）
在拼数字的过程中，我们怎么统计所有数字的波动值之和呢？
假设我们现在已经拼好了前两位 1 和 2。现在要填第三位：如果第三位我们填 0（拼出 120），我们发现：1 < 2 > 0，中间的 2 是一个峰。波动值 +1。
但如果我们要拼一个很大的数，比如总共有 6 位数，我们现在只拼到了前三位 1, 2, 0，后面还有 3 位没有填。如果我们发现 2 是一个峰，那么无论后面 3 位填什么，这个 2 是峰的事实都不会改变。
假设后面 3 位一共有 $100$ 种不同的填法，那就意味着：这 $100$ 个最终拼出来的数字，它们在第二位（数字 2）上都会有一个峰。所以，这一个峰，会为最终的总波动值贡献 $1 \times 100 = 100$ 分。
这就是为什么我们的递归函数要返回两个值：
cnt：后面还能拼出多少个合法的数字。
tot：后面这些数字拼完后，累积的总波动值。
当我们在某一步发现产生了一个峰/谷时，它的贡献就是：1 × (后面能拼出的数字个数 cnt)。我们把这个贡献加到总分里。
第四步：代码中那些变量是干什么的？
在函数 dfs(i, pre2, pre, is_limit, is_num) 中：
i：当前在填第几位。
pre：刚才填的那一位数字（即 B）。
pre2：刚才的前一位数字（即 A）。
is_num：一个标记。因为我们在拼数字时，前面可能会有空位（比如想拼 25，前几位就填 0）。is_num 告诉我们真正的数字是不是已经开始填了。如果还没开始填，就不能去计算峰和谷。
is_limit：一个标记，用来限制我们填的数不能超过 $n u m 2$ 。例如 $n u m 2 = 120$ ，如果我们前两位填了 1 和 2，第三位就受到限制（is_limit 为真），最大只能填 0，不能填 1 到 9。
总结
这个算法的本质是：
树状拼数：从左到右，一位一位填入数字。
窗口滑动：每次填入新数字 d 时，回头看一眼刚填的 pre 和 pre2，判断 pre 是不是波动点。
乘法累加：如果 pre 是波动点，由于后面还有很多位可以任意填，我们直接用“1个波动点 × 后面可能的组合数”，直接把这一批数字的波动值一起算出来，从而省去了挨个计算的时间。

递归和数位 DP 的代码确实比较抽象，因为很多逻辑（比如回溯、状态记录）是被隐藏在递归调用里的。
为了让你彻底看懂，我们把代码拆成几个小片段，并给每一行代码配上最通俗的中文大白话注释。
核心代码的详细拆解与注释
整个算法最核心的是 dfs 这个递归函数。我们把它分成 4 个部分来看：
第一部分：出口（什么时候结束？）
当我们把数字的每一位都填完了，递归就该结束了。
python
# i 是当前填到了第几位，L 是总位数（比如 120 的 L 是 3）
if i == L:
    # 如果 is_num 是 True，说明我们成功拼出了一个有意义的数字（比如 120）
    # 此时，我们找到了 1 个合法的数字，它后面的波动值是 0。
    # 所以返回 (1, 0) -> (找到1个数字, 波动值是0)
    if is_num:
        return (1, 0)
    else:
        # 如果 is_num 是 False，说明我们一整路都在填 0，什么数字都没拼出来
        # 返回 (0, 0) -> (找到0个数字, 波动值是0)
        return (0, 0)
第二部分：确定当前位能填什么数字？
我们要填第 i 位，这一位能填 0~9 里的哪些数？
python
# 1. 确定上限 limit
# 如果受限制 (is_limit 为 True)，当前位最大只能填到 s[i]（上限）
# 如果不受限制 (is_limit 为 False)，当前位可以放胆填到 9
limit = int(s[i]) if is_limit else 9

# 2. 确定下限 low
# 如果之前已经填过数字了 (is_num 为 True)，当前位可以填 0（比如 102 的中间可以填 0）
# 如果之前全是前导零，还没开始填数字 (is_num 为 False)，那我们如果要在这里“开个头”，就必须填 1~9，不能填 0
low = 0 if is_num else 1
第三部分：如果不填数字（继续当成前导零）
如果我们还没开始填任何数字（is_num 是 False），我们可以选择在当前位“什么都不填”（也就是填入前导零，继续往后看）。
python
res_cnt = 0  # 记录从这里开始，后面能拼出多少个合法的数
res_tot = 0  # 记录这些数的总波动值

if not is_num:
    # 既然什么都不填，那前前一位、前一位都还是“不存在”（填 -1）
    # is_limit 变成 False，因为开头填 0 肯定不会超过上限
    c, t = dfs(i + 1, -1, -1, False, False)
    res_cnt += c  # 累加拼出的数字个数
    res_tot += t  # 累加波动点分数
第四部分：如果填入一个数字 d（最核心的计算）
我们要遍历当前位所有可以填的数字 d（从 low 到 limit）。
python
for d in range(low, limit + 1):
    # 1. 下一位是否还要受上限限制？
    # 只有当前受限制，且我们刚好填了上限数字时，下一位才继续受限制
    next_limit = is_limit and (d == limit)
    
    # 2. 核心：检查前一位 (pre) 是不是峰或者谷
    contrib = 0  # 这一次尝试能得到多少个波动点
    
    # 必须之前已经有数字了 (is_num)，且前前一位也存在 (pre2 != -1) 才能凑够 3 个数来判断
    if is_num and pre2 != -1:
        # 如果 pre2 < pre > d (峰) 或者 pre2 > pre < d (谷)
        if (pre2 < pre > d) or (pre2 > pre < d):
            contrib = 1  # 找到了一个波动点！
            
    # 3. 带着当前的信息，继续去填下一位 (i + 1)
    # 此时，原来的 pre 变成了新的 pre2，当前的 d 变成了新的 pre
    c, t = dfs(i + 1, pre, d, next_limit, True)
    
    # 4. 累加结果
    res_cnt += c  # 加上后面拼出的数字个数
    
    # 总分数 = 后面拼出来的分数 t + 当前波动点贡献的分数 (c * contrib)
    # 为什么乘 c？因为后面能拼出 c 个不同的数字，每一个数字都继承了当前这个波动点
    res_tot += (t + c * contrib)
一个极简的例子模拟
假设我们限制最大只能填 120。
第一位填 1：此时 pre = 1, pre2 = -1（前前位还没有）。
第二位填 2：此时 pre = 2, pre2 = 1。依然不能判断，因为还没填第三位。
第三位填 0：此时当前数字 $d = 0$ 。我们开始判断：pre2 是 1，pre 是 2，当前 $d$ 是 0。因为 $1 < 2 > 0$ 成立！所以这是一个峰。 contrib 设为 1。
结束：后面没有位置了，能拼出的数字个数 $c = 1$ （就是 120 本身）。所以这一次贡献的波动值分数为： $c \times c o n t r i b = 1 \times 1 = 1$ 分。
什么是 @cache？
在代码最上面有一行 @cache。这是 Python 里的一个“自动记账本”。因为在递归过程中，我们会遇到很多一模一样的提问（比如：从第 3 位开始，前一位是 5，前前位是 4，不受限制，已经有数字了，后面能拼出多少个波动点？）。如果没有 @cache，程序每次都要重新算一遍；有了 @cache，程序第一次算完会把答案写在“账本”上，下次再遇到相同提问直接报答案，速度会提升成千上万倍。

T3753.范围内总波动值 II

第一步：怎样才算一个“峰”或“谷”？

第二步：为什么要逐位构造数字？

第三步：如何计算总波动值？（核心难点）

第四步：代码中那些变量是干什么的？

总结

核心代码的详细拆解与注释

第一部分：出口（什么时候结束？）

第二部分：确定当前位能填什么数字？

第三部分：如果不填数字（继续当成前导零）

第四部分：如果填入一个数字 `d`（最核心的计算）

一个极简的例子模拟

什么是 `@cache`？

T3753.范围内总波动值 II ​

第一步：怎样才算一个“峰”或“谷”？ ​

第二步：为什么要逐位构造数字？ ​

第三步：如何计算总波动值？（核心难点） ​

第四步：代码中那些变量是干什么的？ ​

总结 ​

核心代码的详细拆解与注释 ​

第一部分：出口（什么时候结束？） ​

第二部分：确定当前位能填什么数字？ ​

第三部分：如果不填数字（继续当成前导零） ​

第四部分：如果填入一个数字 d（最核心的计算） ​

一个极简的例子模拟 ​

什么是 @cache？ ​

T3753.范围内总波动值 II

第一步：怎样才算一个“峰”或“谷”？

第二步：为什么要逐位构造数字？

第三步：如何计算总波动值？（核心难点）

第四步：代码中那些变量是干什么的？

总结

核心代码的详细拆解与注释

第一部分：出口（什么时候结束？）

第二部分：确定当前位能填什么数字？

第三部分：如果不填数字（继续当成前导零）

第四部分：如果填入一个数字 `d`（最核心的计算）

一个极简的例子模拟

什么是 `@cache`？