第一次见到 1416 这道题时我其实是被题目描述里“恢复数组”这个说法吸引的。LeetCode 上很多困难题难点都藏在边界和状态设计里这道题也不例外表面上是字符串分割本质上却是一道非常经典的计数型动态规划而且一不小心就会踩进“前导零”“取模”“枚举范围”三个连环坑里。我会把从题意拆解、状态设计、代码实现到踩坑复盘的全过程都写出来尤其会把网上题解经常一笔带过的“为什么复杂度是线性”这件事讲透。先说清楚这是一道适合用来检验自己 DP 基本功的题。它的输入约束很刁钻字符串长度最大到 10^5整数 k 最大到 10^9所以任何 O(n^2) 的朴素写法都会必死无疑。但一旦你理解了“枚举最后一段并累加前面的方案数”这个核心思想再用对状态定义代码其实不超过二十行。刷这道题的过程相当于把字符串 DP 里的几个经典考点——前导零的判断、溢出的预防、子问题划分的合理性——一次性全部复习一遍。1. 先把题意翻译成人话1.1 题目到底在问什么给你一个纯数字字符串 s 和一个整数 k比如 s 1234k 1000。现在要你把字符串切成若干段每一段都代表一个十进制整数切割之后满足几个条件每个数字必须大于等于 1必须小于等于 k而且不能有前导零。问总共有多少种不同的切法结果很大要对 10^9 7 取模。所谓“恢复数组”可以这样理解原数组本来是一个整数数组比如 [12, 34]每个数字转成字符串后拼接起来就得到 1234。现在你手里只剩拼接后的字符串不知道原来的数组长什么样题目要你统计“有多少种可能的分割方式能还原出一个合法的原数组”。这不是让你输出具体方案而是只问方案数。有一点必须提醒第一次做这道题的朋友s 的长度上限是 10^5k 的上限是 10^9。这意味着最终答案的规模会非常巨大也意味着算法必须在线性或者接近线性的时间内完成。1.2 先拿小例子找感觉看两个比较容易验证的例子。第一个是 s 1000k 1000。如果切成 [1, 000]第二段 000 以 0 开头这是不合法的如果切成 [10, 00]最后一段 00 也不合法所以唯一合法方案是整体作为一段 [1000]答案就是 1。这个小例子直接说明了前导零的杀伤力。第二个是 s 1234k 1000。注意 [1234] 本身不合规因为 1234 1000。合法的分割方法包括 [1, 234]、[12, 34]、[123, 4]、[1, 2, 34]、[1, 23, 4]、[12, 3, 4]、[1, 2, 3, 4]总共 7 种。这个例子能帮你直观感受到同一个字符串会因为切割位置不同产生大量方案这就是为什么必须用动态规划而不是纯枚举。2. 暴力枚举为什么走不通2.1 枚举分割点的代价最朴素的思路很容易想到在字符串的每个字符间隙尝试切或不切一共有 n - 1 个间隙所以方案数最多是 2^(n-1)。哪怕 n 只有 100这个规模也已经让程序当场死给你看更别说 n 10^5。所以这条路从起点就是死的不需要再优化。还有同学会想那我用 DFS 枚举每次递归到下一个切割点只枚举合法的长度不就行了这个想法方向是对的但如果你只是“从当前字符开始尝试切 1 位、2 位......直到数值超过 k”在没有任何记忆化的情况下仍然会有大量重复计算。举一个具体场景s 1234执行 dfs(1) 时可能已经计算过从位置 1 开始的所有方案但后面处理其他分支时又调用了 dfs(1)于是同样的子问题被重复算了一遍又一遍。字符串稍长一点这种重复就会指数级增多。2.2 记忆化之后的问题在哪用备忘录优化 DFS 确实能消除重复计算理论上每个位置最多被完整计算一次看起来复杂度可以接受。但这里有个实际工程里的隐患n 最大 10^5递归深度也可能到 10^5。Python 默认递归深度一般只有 1000 左右直接一跑就是 RecursionErrorC 虽然能通过手动调节但深度递归依然可能爆栈而且调试体验很差。所以在正式题解里我基本不推荐用记忆化递归而是直接用迭代的动态规划。其实这两者的状态转移逻辑是一模一样的只是迭代版不需要维护函数调用栈也天然避免了递归深度的问题。这也是很多人在讨论区反复强调“能用迭代就不要递归”的原因。3. DP 状态设计与转移逻辑3.1 用后缀定义做状态边界会干净很多这道题的状态定义有两种写法一种定义 dp[i] 表示 s 的前缀 s[0..i-1] 能组成的合法方案数另一种定义 dp[i] 表示 s 从 i 开始的子串 s[i..n-1] 能组成的合法方案数。我个人强烈推荐后缀定义因为它在处理“第一段的起点”这个问题时非常自然几乎不会写乱。定义 dp[i] 为从位置 i 到字符串末尾这段子串 s[i..] 的恢复方案数。空串的方案数是 1所以初始化 dp[n] 1。最终答案就是 dp[0]。为什么这样定义舒服因为转移的时候我们只需要枚举“从位置 i 开始的这一段从哪里结束”。假设这一段是 s[i..j]那么切割后剩余部分是 s[j1..]方案数就是 dp[j1]。把所有合法的 j 对应的 dp[j1] 加起来就是 dp[i]。转移方程可以写成dp[i] sum(dp[j1])条件是 j 从 i 开始向后延伸s[i..j] 没有前导零且这段表示的数值 k。如果 s[i] 本身就是 0那么无论这段怎么切第一段都不可能合法因为要么第一段以 0 开头要么单独一个 0 不在 1..k 范围内。此时直接令 dp[i] 0。3.2 单调递增带来的剪枝关键枚举 j 的时候随着 j 往右移动s[i..j] 表示的数值会不断变大而且这个增长是单调的。这一点非常关键它是整个算法能保持线性的核心。我写代码时是这么处理数值的设一个变量 cur初始为 0。每向右扩展一个字符 s[j]就执行 cur cur * 10 (s[j] - 0)。这个操作等于在原来数字的末尾追加一位数字。由于 k 限制是 10^9一旦 cur k那么再往右扩展cur 只会更大不可能再合法因此可以立刻 break 掉内层循环。很多第一次做这题的人会担心如果每次都枚举到 break那最坏不还是 O(n^2) 吗实际上不会。因为 k 10^9最多只有 10 位十进制数字所以从任意位置 i 出发内层循环最多尝试 10 次就必须 break。整体复杂度其实是 O(10n)也就是 O(n)。3.3 取模操作要放在累加里别攒到最后方案数量非常容易爆炸所以每一轮累加都要取模。这里的模数是 10^9 7是一个固定常数。累加时写成 dp[i] (dp[i] dp[j1]) % MOD 即可。关于取模有一点经验不要先在一轮里累加完所有 dp[j1] 再取模。虽然有些语言的大整数能扛住但 C 里 dp[i] 累加多次后完全可能超过 int 甚至 long long 的范围所以每加一次就取模是最稳妥的写法。后面我会在代码里演示。4. 三个必须想清楚的边界细节4.1 前导零不是“包含零”而是“以零开头”这是这道题最容易翻车的点没有之一。举个例子字符串 1001 整体切一刀都不切作为数字 1001只要满足 1001 k它就是合法的。它中间有两个 0完全不碍事。但如果把它切成 [1, 001]第二段 001 以 0 开头就不合法。还有如果切成 [10, 01]后面的 01 也不合法。所以前导零的判断不是“这段中有没有 0”而是“这段的第一个字符是不是 0”。在代码里当 s[i] 0 时任何从 i 开始的一段都绝对不可能合法直接跳过。这是一个非常干脆的剪枝比在循环里逐个判断要快得多。我之前见过有初学者把状态定义成前缀 dp然后在转移时看到 s[i-1] 0 就给 dp[i] 0结果 s 10 的时候怎么都跑不对。原因就是 [10] 这个合法方案里最后一个字符是 0但它和前面的 1 组合在一起是合法的。用后缀定义之后这种纠结完全消失了。4.2 为什么单独一个 0 总是不合法题目条件说每个数字必须在 1 到 k 之间所以数字 0 本身不合法。而且包含前导零的0xxx也不合法。因此在代码里遇到 s[i] 0 时直接 continue 或者直接置 dp[i] 0。这里还要注意一个衍生问题当我们枚举一段 s[i..j] 时如果 s[i] ! 0即使后面跟着若干个 0也先不用管只要整段的数值不超过 k 就算合法。因为前导零的判断只取决于第一个字符。4.3 不同语言的数值溢出陷阱C 选手请特别注意int 在常见环境下最大只有 21 亿左右而 10^9 7 取模之后的结果虽然不会超过 10^9但 cur 在拼接数字时可能超过 int 范围。比如 cur 已经是 999999999再追加一位 9中间值会达到 9999999999这已经超过 int 了。所以 cur 必须用 long long 来存。dp 数组本身每个值都小于 MOD两个小 MOD 值相加也不会超过 2 * 10^9int 还能扛住但为了统一和安全我一般会把 dp 也声明成 long long或者干脆在使用时强转。Java 里对应的是 longPython 则完全不用操心因为 Python 的大整数会自动扩展。5. 完整代码与逐行解析5.1 C 参考实现下面这份 C 代码可以直接提交通过注释写得比较详细class Solution { public: int numberOfArrays(string s, int k) { const int MOD 1000000007; int n s.size(); vectorlong long dp(n 1, 0); dp[n] 1; // 空串分割方案为 1 for (int i n - 1; i 0; --i) { if (s[i] 0) { // 从 i 开始的任何合法段第一个字符都不能是 0 continue; } long long cur 0; for (int j i; j n; j) { cur cur * 10 (s[j] - 0); if (cur k) { break; // 再往右只会更大直接剪枝 } dp[i] (dp[i] dp[j 1]) % MOD; } } return (int)dp[0]; } };注意内层循环里 j 1 代表的是这一段 s[i..j] 切割后剩余部分 s[j1..] 的起始位置。dp[i] 累加的是“当前这一段的种数乘以后续所有方案数”而 dp[j1] 已经包含了后续的所有方案所以直接相加。5.2 Python 参考实现Python 版本几乎可以照抄思路但有一个小优化把 int(s[j]) 换成 ord(s[j]) - ord(0)速度会快一些class Solution: def numberOfArrays(self, s: str, k: int) - int: MOD 10**9 7 n len(s) dp [0] * (n 1) dp[n] 1 for i in range(n - 1, -1, -1): if s[i] 0: continue cur 0 for j in range(i, n): cur cur * 10 ord(s[j]) - ord(0) if cur k: break dp[i] (dp[i] dp[j 1]) % MOD return dp[0]Python 的取模用 % MOD因为 dp[i] 累加的都是已经取过模的值所以在此处加法不会溢出但取模仍不可省略。5.3 手推一遍 dp 数组拿前面举过的 s 1234, k 1000 来实际推演一遍你会看到倒推过程非常清晰dp[4] 1代表空串。i 3s[3] 4。cur 4 1000dp[3] dp[4]得到 dp[3] 1。这表示 4 只有一种方案。i 2s[2] 3。cur 3dp[2] dp[3] 1再追加 4cur 34dp[2] dp[4] 1最后 dp[2] 2。对应 3|4 和 34。i 1s[1] 2。cur 2dp[1] dp[2] 2追加 3cur 23dp[1] dp[3] 1再追加 4cur 234dp[1] dp[4] 1最后 dp[1] 4。i 0s[0] 1。cur 1dp[0] dp[1] 4追加 2cur 12dp[0] dp[2] 2追加 3cur 123dp[0] dp[3] 1再追加 4cur 1234 1000break。最终 dp[0] 7。这个手推过程也验证了整体的答案 7 正好等于“第一段只取 1 时的 4 种方案 第一段取 12 时的 2 种方案 第一段取 123 时的 1 种方案”思路非常直观。6. 常见问题与排查技巧实录6.1 我这边的坑坑洼洼清单做这道题时我在讨论区看到不少人遇到的典型问题结合自己的 debug 经历整理成下面这个速查表症状可能原因解决方案答案偏小很多中间结果用 int 存拼接数字时溢出cur 全部使用 long long全 0 字符串答案不为 0没有检查 s[i] 0 就进入转移遇到 0 直接 continues 10 这类用例出错用了前缀定义但没处理好末尾 0 的情况改用后缀定义 dp[i] 表示 s[i..] 的方案数内层循环不敢 break以为 break 会漏掉合法方案数字越拼越大超过 k 后必然不合法放心 break递归实现爆栈用记忆化递归深度达到 10^5改成迭代 DP不要跟栈过不去忘记取模直接累加所有 dp[j1]每加一次就 % MOD6.2 记忆化 DFS 到底能不能用我在写这题时最开始其实是用记忆化 DFS 过的因为当时觉得递归写起来更顺手。对于 n 10^5 的输入只要把递归深度调大是可以通过的。Python 里要加 sys.setrecursionlimit(10**6)C 里虽然没这个限制但深度递归会占用大量调用栈调试时一旦 Segmentation fault很难快速定位是逻辑错误还是栈溢出。所以我给读者的建议是比赛或面试时用迭代 DP 表达同样的状态转移逻辑代码更短还不容易踩坑。递归的写法只适合用来在草稿纸上推演状态转移真正提交代码时用迭代版。6.3 这类题我要不要记一堆模板字符串分割计数题其实是有一类共性的。除了 1416LeetCode 上还有 91. 解码方法、剑指 Offer 46. 把数字翻译成字符串、639. 解码方法 II 等核心模式都是“枚举最后一段累加剩余部分的方案”。区别只在于转移的约束不同91 题看单个数字和双位数字是否为合法字母编码1416 题看当前这段拼出来的数字是否在 1..k 之间。所以不需要背模板而是把“当前位置 i 作为最后一段的起点/终点”这个思路理解透遇到新的约束条件时改判断逻辑就行。7. 从这道题能带走什么7.1 字符串 DP 的一个通用套路我的习惯是看到“把一个字符串分成若干段每段满足某个条件问方案数”这种题先想两件事第一状态定义里放位置还是放剩余长度第二转移时枚举的是“最后一段的起点”还是“最后一段的终点”。1416 给了我们一个很好的示范用后缀定义从后往前倒推枚举当前段的终点然后累加后续方案。这个套路在后缀问题里非常统一。如果你能在一道困难题里把状态定义这件事一次想对后面相似题目基本都能套用同一个思维框架。7.2 数值上限是天然的剪枝器这道题让我印象最深的一个点其实是“k 的范围决定了每个状态的转移次数上限”。很多时候我们把精力放在优化状态设计上却忽略了题目给的数据范围本身就蕴含了很强的剪枝信息。k 10^9意味着每个起点最多只可能扩展 10 位数字这比任何高级优化技巧都更直接。以后再看类似题目时我会先花 30 秒看清楚输入上限再决定算法。如果数值上限很小往往可以用暴力的方式枚举数值如果字符串很长但数值上限很紧那么从每个位置向后枚举一小段就是合理的。7.3 一次 Debug 经历给我的教训我卡得最久的一次是忘记在 dp 数组里处理 s[i] 0 的情况导致样例 s 1000 的答案变成了 2而不是 1。当时我反复检查转移方程怎么想都觉得没错后来打印 dp 数组才发现位置 1 和位置 2 的子串 000、00 因为我没跳过 0被错误地计算成了合法方案。从那以后我写这类字符串数字分割的题会先把“前导零特判”写在状态转移的最前面作为第一道闸门。这是一个下意识动作几乎可以杜绝一大类错误。说到底1416 这道题本身不难难的在于细节的严密性。我的体会是动规题不要急着写代码先把状态定义写在纸上用一个小样例从头到尾手推一遍 dp确保每步的转移都符合题意再动手敲代码。这样看起来多花了五分钟实际上省掉了后面无穷无尽的调试时间。这套方法论我后来用在所有字符串 DP 题目上几乎没有失手过。 LeetCode 1416 恢复数组：字符串分割中的计数型动态规划
第一次见到 1416 这道题时我其实是被题目描述里“恢复数组”这个说法吸引的。LeetCode 上很多困难题难点都藏在边界和状态设计里这道题也不例外表面上是字符串分割本质上却是一道非常经典的计数型动态规划而且一不小心就会踩进“前导零”“取模”“枚举范围”三个连环坑里。我会把从题意拆解、状态设计、代码实现到踩坑复盘的全过程都写出来尤其会把网上题解经常一笔带过的“为什么复杂度是线性”这件事讲透。先说清楚这是一道适合用来检验自己 DP 基本功的题。它的输入约束很刁钻字符串长度最大到 10^5整数 k 最大到 10^9所以任何 O(n^2) 的朴素写法都会必死无疑。但一旦你理解了“枚举最后一段并累加前面的方案数”这个核心思想再用对状态定义代码其实不超过二十行。刷这道题的过程相当于把字符串 DP 里的几个经典考点——前导零的判断、溢出的预防、子问题划分的合理性——一次性全部复习一遍。1. 先把题意翻译成人话1.1 题目到底在问什么给你一个纯数字字符串 s 和一个整数 k比如 s 1234k 1000。现在要你把字符串切成若干段每一段都代表一个十进制整数切割之后满足几个条件每个数字必须大于等于 1必须小于等于 k而且不能有前导零。问总共有多少种不同的切法结果很大要对 10^9 7 取模。所谓“恢复数组”可以这样理解原数组本来是一个整数数组比如 [12, 34]每个数字转成字符串后拼接起来就得到 1234。现在你手里只剩拼接后的字符串不知道原来的数组长什么样题目要你统计“有多少种可能的分割方式能还原出一个合法的原数组”。这不是让你输出具体方案而是只问方案数。有一点必须提醒第一次做这道题的朋友s 的长度上限是 10^5k 的上限是 10^9。这意味着最终答案的规模会非常巨大也意味着算法必须在线性或者接近线性的时间内完成。1.2 先拿小例子找感觉看两个比较容易验证的例子。第一个是 s 1000k 1000。如果切成 [1, 000]第二段 000 以 0 开头这是不合法的如果切成 [10, 00]最后一段 00 也不合法所以唯一合法方案是整体作为一段 [1000]答案就是 1。这个小例子直接说明了前导零的杀伤力。第二个是 s 1234k 1000。注意 [1234] 本身不合规因为 1234 1000。合法的分割方法包括 [1, 234]、[12, 34]、[123, 4]、[1, 2, 34]、[1, 23, 4]、[12, 3, 4]、[1, 2, 3, 4]总共 7 种。这个例子能帮你直观感受到同一个字符串会因为切割位置不同产生大量方案这就是为什么必须用动态规划而不是纯枚举。2. 暴力枚举为什么走不通2.1 枚举分割点的代价最朴素的思路很容易想到在字符串的每个字符间隙尝试切或不切一共有 n - 1 个间隙所以方案数最多是 2^(n-1)。哪怕 n 只有 100这个规模也已经让程序当场死给你看更别说 n 10^5。所以这条路从起点就是死的不需要再优化。还有同学会想那我用 DFS 枚举每次递归到下一个切割点只枚举合法的长度不就行了这个想法方向是对的但如果你只是“从当前字符开始尝试切 1 位、2 位......直到数值超过 k”在没有任何记忆化的情况下仍然会有大量重复计算。举一个具体场景s 1234执行 dfs(1) 时可能已经计算过从位置 1 开始的所有方案但后面处理其他分支时又调用了 dfs(1)于是同样的子问题被重复算了一遍又一遍。字符串稍长一点这种重复就会指数级增多。2.2 记忆化之后的问题在哪用备忘录优化 DFS 确实能消除重复计算理论上每个位置最多被完整计算一次看起来复杂度可以接受。但这里有个实际工程里的隐患n 最大 10^5递归深度也可能到 10^5。Python 默认递归深度一般只有 1000 左右直接一跑就是 RecursionErrorC 虽然能通过手动调节但深度递归依然可能爆栈而且调试体验很差。所以在正式题解里我基本不推荐用记忆化递归而是直接用迭代的动态规划。其实这两者的状态转移逻辑是一模一样的只是迭代版不需要维护函数调用栈也天然避免了递归深度的问题。这也是很多人在讨论区反复强调“能用迭代就不要递归”的原因。3. DP 状态设计与转移逻辑3.1 用后缀定义做状态边界会干净很多这道题的状态定义有两种写法一种定义 dp[i] 表示 s 的前缀 s[0..i-1] 能组成的合法方案数另一种定义 dp[i] 表示 s 从 i 开始的子串 s[i..n-1] 能组成的合法方案数。我个人强烈推荐后缀定义因为它在处理“第一段的起点”这个问题时非常自然几乎不会写乱。定义 dp[i] 为从位置 i 到字符串末尾这段子串 s[i..] 的恢复方案数。空串的方案数是 1所以初始化 dp[n] 1。最终答案就是 dp[0]。为什么这样定义舒服因为转移的时候我们只需要枚举“从位置 i 开始的这一段从哪里结束”。假设这一段是 s[i..j]那么切割后剩余部分是 s[j1..]方案数就是 dp[j1]。把所有合法的 j 对应的 dp[j1] 加起来就是 dp[i]。转移方程可以写成dp[i] sum(dp[j1])条件是 j 从 i 开始向后延伸s[i..j] 没有前导零且这段表示的数值 k。如果 s[i] 本身就是 0那么无论这段怎么切第一段都不可能合法因为要么第一段以 0 开头要么单独一个 0 不在 1..k 范围内。此时直接令 dp[i] 0。3.2 单调递增带来的剪枝关键枚举 j 的时候随着 j 往右移动s[i..j] 表示的数值会不断变大而且这个增长是单调的。这一点非常关键它是整个算法能保持线性的核心。我写代码时是这么处理数值的设一个变量 cur初始为 0。每向右扩展一个字符 s[j]就执行 cur cur * 10 (s[j] - 0)。这个操作等于在原来数字的末尾追加一位数字。由于 k 限制是 10^9一旦 cur k那么再往右扩展cur 只会更大不可能再合法因此可以立刻 break 掉内层循环。很多第一次做这题的人会担心如果每次都枚举到 break那最坏不还是 O(n^2) 吗实际上不会。因为 k 10^9最多只有 10 位十进制数字所以从任意位置 i 出发内层循环最多尝试 10 次就必须 break。整体复杂度其实是 O(10n)也就是 O(n)。3.3 取模操作要放在累加里别攒到最后方案数量非常容易爆炸所以每一轮累加都要取模。这里的模数是 10^9 7是一个固定常数。累加时写成 dp[i] (dp[i] dp[j1]) % MOD 即可。关于取模有一点经验不要先在一轮里累加完所有 dp[j1] 再取模。虽然有些语言的大整数能扛住但 C 里 dp[i] 累加多次后完全可能超过 int 甚至 long long 的范围所以每加一次就取模是最稳妥的写法。后面我会在代码里演示。4. 三个必须想清楚的边界细节4.1 前导零不是“包含零”而是“以零开头”这是这道题最容易翻车的点没有之一。举个例子字符串 1001 整体切一刀都不切作为数字 1001只要满足 1001 k它就是合法的。它中间有两个 0完全不碍事。但如果把它切成 [1, 001]第二段 001 以 0 开头就不合法。还有如果切成 [10, 01]后面的 01 也不合法。所以前导零的判断不是“这段中有没有 0”而是“这段的第一个字符是不是 0”。在代码里当 s[i] 0 时任何从 i 开始的一段都绝对不可能合法直接跳过。这是一个非常干脆的剪枝比在循环里逐个判断要快得多。我之前见过有初学者把状态定义成前缀 dp然后在转移时看到 s[i-1] 0 就给 dp[i] 0结果 s 10 的时候怎么都跑不对。原因就是 [10] 这个合法方案里最后一个字符是 0但它和前面的 1 组合在一起是合法的。用后缀定义之后这种纠结完全消失了。4.2 为什么单独一个 0 总是不合法题目条件说每个数字必须在 1 到 k 之间所以数字 0 本身不合法。而且包含前导零的0xxx也不合法。因此在代码里遇到 s[i] 0 时直接 continue 或者直接置 dp[i] 0。这里还要注意一个衍生问题当我们枚举一段 s[i..j] 时如果 s[i] ! 0即使后面跟着若干个 0也先不用管只要整段的数值不超过 k 就算合法。因为前导零的判断只取决于第一个字符。4.3 不同语言的数值溢出陷阱C 选手请特别注意int 在常见环境下最大只有 21 亿左右而 10^9 7 取模之后的结果虽然不会超过 10^9但 cur 在拼接数字时可能超过 int 范围。比如 cur 已经是 999999999再追加一位 9中间值会达到 9999999999这已经超过 int 了。所以 cur 必须用 long long 来存。dp 数组本身每个值都小于 MOD两个小 MOD 值相加也不会超过 2 * 10^9int 还能扛住但为了统一和安全我一般会把 dp 也声明成 long long或者干脆在使用时强转。Java 里对应的是 longPython 则完全不用操心因为 Python 的大整数会自动扩展。5. 完整代码与逐行解析5.1 C 参考实现下面这份 C 代码可以直接提交通过注释写得比较详细class Solution { public: int numberOfArrays(string s, int k) { const int MOD 1000000007; int n s.size(); vectorlong long dp(n 1, 0); dp[n] 1; // 空串分割方案为 1 for (int i n - 1; i 0; --i) { if (s[i] 0) { // 从 i 开始的任何合法段第一个字符都不能是 0 continue; } long long cur 0; for (int j i; j n; j) { cur cur * 10 (s[j] - 0); if (cur k) { break; // 再往右只会更大直接剪枝 } dp[i] (dp[i] dp[j 1]) % MOD; } } return (int)dp[0]; } };注意内层循环里 j 1 代表的是这一段 s[i..j] 切割后剩余部分 s[j1..] 的起始位置。dp[i] 累加的是“当前这一段的种数乘以后续所有方案数”而 dp[j1] 已经包含了后续的所有方案所以直接相加。5.2 Python 参考实现Python 版本几乎可以照抄思路但有一个小优化把 int(s[j]) 换成 ord(s[j]) - ord(0)速度会快一些class Solution: def numberOfArrays(self, s: str, k: int) - int: MOD 10**9 7 n len(s) dp [0] * (n 1) dp[n] 1 for i in range(n - 1, -1, -1): if s[i] 0: continue cur 0 for j in range(i, n): cur cur * 10 ord(s[j]) - ord(0) if cur k: break dp[i] (dp[i] dp[j 1]) % MOD return dp[0]Python 的取模用 % MOD因为 dp[i] 累加的都是已经取过模的值所以在此处加法不会溢出但取模仍不可省略。5.3 手推一遍 dp 数组拿前面举过的 s 1234, k 1000 来实际推演一遍你会看到倒推过程非常清晰dp[4] 1代表空串。i 3s[3] 4。cur 4 1000dp[3] dp[4]得到 dp[3] 1。这表示 4 只有一种方案。i 2s[2] 3。cur 3dp[2] dp[3] 1再追加 4cur 34dp[2] dp[4] 1最后 dp[2] 2。对应 3|4 和 34。i 1s[1] 2。cur 2dp[1] dp[2] 2追加 3cur 23dp[1] dp[3] 1再追加 4cur 234dp[1] dp[4] 1最后 dp[1] 4。i 0s[0] 1。cur 1dp[0] dp[1] 4追加 2cur 12dp[0] dp[2] 2追加 3cur 123dp[0] dp[3] 1再追加 4cur 1234 1000break。最终 dp[0] 7。这个手推过程也验证了整体的答案 7 正好等于“第一段只取 1 时的 4 种方案 第一段取 12 时的 2 种方案 第一段取 123 时的 1 种方案”思路非常直观。6. 常见问题与排查技巧实录6.1 我这边的坑坑洼洼清单做这道题时我在讨论区看到不少人遇到的典型问题结合自己的 debug 经历整理成下面这个速查表症状可能原因解决方案答案偏小很多中间结果用 int 存拼接数字时溢出cur 全部使用 long long全 0 字符串答案不为 0没有检查 s[i] 0 就进入转移遇到 0 直接 continues 10 这类用例出错用了前缀定义但没处理好末尾 0 的情况改用后缀定义 dp[i] 表示 s[i..] 的方案数内层循环不敢 break以为 break 会漏掉合法方案数字越拼越大超过 k 后必然不合法放心 break递归实现爆栈用记忆化递归深度达到 10^5改成迭代 DP不要跟栈过不去忘记取模直接累加所有 dp[j1]每加一次就 % MOD6.2 记忆化 DFS 到底能不能用我在写这题时最开始其实是用记忆化 DFS 过的因为当时觉得递归写起来更顺手。对于 n 10^5 的输入只要把递归深度调大是可以通过的。Python 里要加 sys.setrecursionlimit(10**6)C 里虽然没这个限制但深度递归会占用大量调用栈调试时一旦 Segmentation fault很难快速定位是逻辑错误还是栈溢出。所以我给读者的建议是比赛或面试时用迭代 DP 表达同样的状态转移逻辑代码更短还不容易踩坑。递归的写法只适合用来在草稿纸上推演状态转移真正提交代码时用迭代版。6.3 这类题我要不要记一堆模板字符串分割计数题其实是有一类共性的。除了 1416LeetCode 上还有 91. 解码方法、剑指 Offer 46. 把数字翻译成字符串、639. 解码方法 II 等核心模式都是“枚举最后一段累加剩余部分的方案”。区别只在于转移的约束不同91 题看单个数字和双位数字是否为合法字母编码1416 题看当前这段拼出来的数字是否在 1..k 之间。所以不需要背模板而是把“当前位置 i 作为最后一段的起点/终点”这个思路理解透遇到新的约束条件时改判断逻辑就行。7. 从这道题能带走什么7.1 字符串 DP 的一个通用套路我的习惯是看到“把一个字符串分成若干段每段满足某个条件问方案数”这种题先想两件事第一状态定义里放位置还是放剩余长度第二转移时枚举的是“最后一段的起点”还是“最后一段的终点”。1416 给了我们一个很好的示范用后缀定义从后往前倒推枚举当前段的终点然后累加后续方案。这个套路在后缀问题里非常统一。如果你能在一道困难题里把状态定义这件事一次想对后面相似题目基本都能套用同一个思维框架。7.2 数值上限是天然的剪枝器这道题让我印象最深的一个点其实是“k 的范围决定了每个状态的转移次数上限”。很多时候我们把精力放在优化状态设计上却忽略了题目给的数据范围本身就蕴含了很强的剪枝信息。k 10^9意味着每个起点最多只可能扩展 10 位数字这比任何高级优化技巧都更直接。以后再看类似题目时我会先花 30 秒看清楚输入上限再决定算法。如果数值上限很小往往可以用暴力的方式枚举数值如果字符串很长但数值上限很紧那么从每个位置向后枚举一小段就是合理的。7.3 一次 Debug 经历给我的教训我卡得最久的一次是忘记在 dp 数组里处理 s[i] 0 的情况导致样例 s 1000 的答案变成了 2而不是 1。当时我反复检查转移方程怎么想都觉得没错后来打印 dp 数组才发现位置 1 和位置 2 的子串 000、00 因为我没跳过 0被错误地计算成了合法方案。从那以后我写这类字符串数字分割的题会先把“前导零特判”写在状态转移的最前面作为第一道闸门。这是一个下意识动作几乎可以杜绝一大类错误。说到底1416 这道题本身不难难的在于细节的严密性。我的体会是动规题不要急着写代码先把状态定义写在纸上用一个小样例从头到尾手推一遍 dp确保每步的转移都符合题意再动手敲代码。这样看起来多花了五分钟实际上省掉了后面无穷无尽的调试时间。这套方法论我后来用在所有字符串 DP 题目上几乎没有失手过。