LeetCode 1416. Restore The Array【记忆化搜索,动态规划】困难

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件，我还建立了相关的仓库：https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中，你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等，还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解，还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动，欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

某个程序本来应该输出一个整数数组。但这个程序忘记输出空格了以致输出了一个数字字符串，我们所知道的信息只有：数组中所有整数都在 [1, k] 之间，且数组中的数字都没有前导 0 。

给你字符串 s 和整数 k 。可能会有多种不同的数组恢复结果。

按照上述程序，请你返回所有可能输出字符串 s 的数组方案数。

由于数组方案数可能会很大，请你返回它对 10^9 + 7 取余 后的结果。

示例 1：

输入：s = "1000", k = 10000
输出：1
解释：唯一一种可能的数组方案是 [1000]

示例 2：

输入：s = "1000", k = 10
输出：0
解释：不存在任何数组方案满足所有整数都 >= 1 且 <= 10 同时输出结果为 s 。

示例 3：

输入：s = "1317", k = 2000
输出：8
解释：可行的数组方案为 [1317]，[131,7]，[13,17]，[1,317]，[13,1,7]，[1,31,7]，[1,3,17]，[1,3,1,7]`

示例 4：

输入：s = "2020", k = 30
输出：1
解释：唯一可能的数组方案是 [20,20] 。 [2020] 不是可行的数组方案，原因是 2020 > 30 。 [2,020] 也不是可行的数组方案，因为 020 含有前导 0 。

示例 5：

输入：s = "1234567890", k = 90
输出：34

提示：

• 1 <= s.length <= 10^5.
• s 只包含数字且不包含前导 0 。
• 1 <= k <= 10^9.

解法1 记忆化搜索

对于 s = "1317", k = 2000 ，最后一个整数可以是 7, 17, 217， 1317（值不能超过 $k=2000$ ）。去掉这段恢复的整数，例如去掉 7 后，剩下要解决的问题就是「求出 s = "131", k = 2000 的数组恢复方案数」。这是一个和原问题相似的子问题，所以可以用递归解决。

根据上面的讨论，递归参数只需要一个 i ，dfs(i) 表示把 s[0:i] 这段字符串恢复为数组的方案数。恢复最后的一个整数（不能超过 $k$ ，也不能有前导零）后，假设该整数在字符串 s 中的开始下标为 j ，那么 s[j:i] 就是这个整数的字符串形式，以该整数结尾的 s[0:i] 的恢复方案为 dfs(j - 1) 。

考虑「能恢复的最后一个整数」的不同开始下标 $j$ ，取这些恢复方案数 $dfs(j-1)$ 之和，就是 $dfs(i)$ ，即：
d f s ( i ) = ∑ 1 ≤ s t o i ( s [ j : i ] ) ≤ k & & s [ j ] ≠ ′ 0 ′ i { d f s ( j − 1 ) } dfs(i) = \\sum_{1\\le stoi(s[j\\ :\\ i])\\le k\\ \\&\\& s[j]\\ \\ne\\ '0' }^{i} \\Bigg\\{ dfs(j - 1) \\Bigg\\} dfs(i)=1≤stoi(s[j : i])≤k &&s[j] = ′0′∑i​{dfs(j−1)}

• 递归边界：$dfs(-1)=1$ 。由于 $s$ 中只包含「没有前导零的 $\ge 1$ 的整数」，而 $s$ 的长度 $\ge 1$ ，所以当 $s.size()$ 为 $1$ 时，包含的那个整数必然为 $1\sim 9$ ，恢复方案数为 $1$ 。但恢复数字到 $j=0$ 时需要考虑 $dfs(-1)$ ，我们就将 $dfs(-1)$ 作为边界，并设为 $1$ 。
• 递归入口：$dfs(n-1)$ ，就是答案。

特别地，「先恢复 $s[j+2:i]$ 为整数、再恢复 $s[j:j+1]$ 为整数」和「恢复 $s[j:i]$ 为整数」，都会递归到 $dfs(j-1)$ 。因此可知，整个递归中有大量重复递归调用（递归入参相同），由于递归函数没有副作用，同样的入参无论计算多少次，算出来的结果都是一样的，因此可以用记忆化搜索来优化。

class Solution { 
public:int numberOfArrays(string s, int k) {const int mod = 1e9 + 7;vector<int> dp(s.size()); dp[0] = 1; // 边界  function<int(int)> dfs = [&](int i) -> int { if (i < 0) return 1;if (dp[i]) return dp[i];  long long val = 0, base = 1; // 避免溢出for (int j = i; j >= 0; --j) {val = (s[j] - '0') * base + val;base *= 10; if (base > 1e9 || val > k) break; // 超过题目数据范围if (s[j] != '0') dp[i] = (dp[i] + dfs(j - 1)) % mod;} return dp[i];};return dfs(s.size() - 1);}
}; 

解法2 动态规划

这里将状态数组右移一位，$dp[0]=1$ 相当于 $dfs(-1)$ ：

class Solution { 
public:int numberOfArrays(string s, int k) {const int mod = 1e9 + 7;int n = s.size();vector<int> dp(n + 1); dp[0] = 1; // 边界  for (int i = 0; i < n; ++i) {long long val = 0, base = 1; // 避免溢出for (int j = i; j >= 0; --j) {val = (s[j] - '0') * base + val;base *= 10;if (base > 1e9 || val > k) break; // 超过题目数据范围if (s[j] != '0') dp[i + 1] = (dp[i + 1] + dp[j]) % mod;}}      return dp[n];}
}; 

手机网游