第一次见到 1416 这道题时，我其实是被题目描述里“恢复数组”这个说法吸引的。LeetCode 上很多困难题难点都藏在边界和状态设计里，这道题也不例外：表面上是字符串分割，本质上却是一道非常经典的计数型动态规划，而且一不小心就会踩进“前导零”“取模”“枚举范围”三个连环坑里。我会把从题意拆解、状态设计、代码实现到踩坑复盘的全过程都写出来，尤其会把网上题解经常一笔带过的“为什么复杂度是线性”这件事讲透。
先说清楚：这是一道适合用来检验自己 DP 基本功的题。它的输入约束很刁钻，字符串长度最大到 10^5，整数 k 最大到 10^9，所以任何 O(n^2) 的朴素写法都会必死无疑。但一旦你理解了“枚举最后一段并累加前面的方案数”这个核心思想，再用对状态定义，代码其实不超过二十行。刷这道题的过程，相当于把字符串 DP 里的几个经典考点——前导零的判断、溢出的预防、子问题划分的合理性——一次性全部复习一遍。
1. 先把题意翻译成人话
1.1 题目到底在问什么
给你一个纯数字字符串 s 和一个整数 k，比如 s = "1234"，k = 1000。现在要你把字符串切成若干段，每一段都代表一个十进制整数，切割之后满足几个条件：每个数字必须大于等于 1，必须小于等于 k，而且不能有前导零。问：总共有多少种不同的切法？结果很大，要对 10^9 + 7 取模。
所谓“恢复数组”，可以这样理解：原数组本来是一个整数数组，比如 [12, 34]，每个数字转成字符串后拼接起来就得到 "1234"。现在你手里只剩拼接后的字符串，不知道原来的数组长什么样，题目要你统计“有多少种可能的分割方式能还原出一个合法的原数组”。这不是让你输出具体方案，而是只问方案数。
有一点必须提醒第一次做这道题的朋友：s 的长度上限是 10^5，k 的上限是 10^9。这意味着最终答案的规模会非常巨大，也意味着算法必须在线性或者接近线性的时间内完成。
1.2 先拿小例子找感觉
看两个比较容易验证的例子。
第一个是 s = "1000"，k = 1000。如果切成 [1, 000]，第二段 "000" 以 0 开头，这是不合法的；如果切成 [10, 00]，最后一段 "00" 也不合法；所以唯一合法方案是整体作为一段 [1000]，答案就是 1。这个小例子直接说明了前导零的杀伤力。
第二个是 s = "1234"，k = 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 左右，直接一跑就是 RecursionError；C++ 虽然能通过手动调节，但深度递归依然可能爆栈，而且调试体验很差。
所以在正式题解里我基本不推荐用记忆化递归，而是直接用迭代的动态规划。其实这两者的状态转移逻辑是一模一样的，只是迭代版不需要维护函数调用栈，也天然避免了递归深度的问题。这也是很多人在讨论区反复强调“能用迭代就不要递归”的原因。
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[j+1..]，方案数就是 dp[j+1]。把所有合法的 j 对应的 dp[j+1] 加起来，就是 dp[i]。
转移方程可以写成：
dp[i] = sum(dp[j+1])，条件是 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[j+1]) % MOD 即可。
关于取模有一点经验：不要先在一轮里累加完所有 dp[j+1] 再取模。虽然有些语言的大整数能扛住，但 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^9，int 还能扛住，但为了统一和安全，我一般会把 dp 也声明成 long long，或者干脆在使用时强转。Java 里对应的是 long，Python 则完全不用操心，因为 Python 的大整数会自动扩展。
5. 完整代码与逐行解析
5.1 C++ 参考实现
下面这份 C++ 代码可以直接提交通过，注释写得比较详细：
class Solution { public: int numberOfArrays(string s, int k) { const int MOD = 1000000007; int n = s.size(); vector<long 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[j+1..] 的起始位置。dp[i] 累加的是“当前这一段的种数乘以后续所有方案数”，而 dp[j+1] 已经包含了后续的所有方案，所以直接相加。
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 = 3，s[3] = '4'。cur = 4 <= 1000，dp[3] += dp[4]，得到 dp[3] = 1。这表示 "4" 只有一种方案。
- i = 2，s[2] = '3'。cur = 3，dp[2] += dp[3] = 1；再追加 '4'，cur = 34，dp[2] += dp[4] = 1，最后 dp[2] = 2。对应 "3|4" 和 "34"。
- i = 1，s[1] = '2'。cur = 2，dp[1] += dp[2] = 2；追加 '3'，cur = 23，dp[1] += dp[3] = 1；再追加 '4'，cur = 234，dp[1] += dp[4] = 1，最后 dp[1] = 4。
- i = 0，s[0] = '1'。cur = 1，dp[0] += dp[1] = 4；追加 '2'，cur = 12，dp[0] += dp[2] = 2；追加 '3'，cur = 123，dp[0] += dp[3] = 1；再追加 '4'，cur = 1234 > 1000，break。最终 dp[0] = 7。
这个手推过程也验证了：整体的答案 7 正好等于“第一段只取 1 时的 4 种方案 + 第一段取 12 时的 2 种方案 + 第一段取 123 时的 1 种方案”，思路非常直观。
6. 常见问题与排查技巧实录
6.1 我这边的坑坑洼洼清单
做这道题时我在讨论区看到不少人遇到的典型问题，结合自己的 debug 经历，整理成下面这个速查表：
| 症状 | 可能原因 | 解决方案 |
|---|---|---|
| 答案偏小很多 | 中间结果用 int 存，拼接数字时溢出 | cur 全部使用 long long |
| 全 0 字符串答案不为 0 | 没有检查 s[i] == '0' 就进入转移 | 遇到 '0' 直接 continue |
| s = "10" 这类用例出错 | 用了前缀定义但没处理好末尾 0 的情况 | 改用后缀定义 dp[i] 表示 s[i..] 的方案数 |
| 内层循环不敢 break | 以为 break 会漏掉合法方案 | 数字越拼越大，超过 k 后必然不合法，放心 break |
| 递归实现爆栈 | 用记忆化递归，深度达到 10^5 | 改成迭代 DP，不要跟栈过不去 |
| 忘记取模 | 直接累加所有 dp[j+1] | 每加一次就 % MOD |
6.2 记忆化 DFS 到底能不能用
我在写这题时最开始其实是用记忆化 DFS 过的，因为当时觉得递归写起来更顺手。对于 n = 10^5 的输入，只要把递归深度调大，是可以通过的。Python 里要加 sys.setrecursionlimit(10**6)，C++ 里虽然没这个限制，但深度递归会占用大量调用栈，调试时一旦 Segmentation fault，很难快速定位是逻辑错误还是栈溢出。
所以我给读者的建议是：比赛或面试时，用迭代 DP 表达同样的状态转移逻辑，代码更短，还不容易踩坑。递归的写法只适合用来在草稿纸上推演状态转移，真正提交代码时用迭代版。
6.3 这类题我要不要记一堆模板
字符串分割计数题其实是有一类共性的。除了 1416，LeetCode 上还有 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 题目上，几乎没有失手过。
