题目大意：
恢复数组
某个程序本来应该输出一个整数数组。但是这个程序忘记输出空格了以致输出了一个数字字符串，我们所知道的信息只有：数组中所有整数都在 [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.
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1416
解题思路分析：
这道题是标准的dp题目，使用递归加记忆数组的方式来解题非常轻松，可以算是模板级别的题目。
本题实际上是以不同的方式分割字符串，使得分割后的每一部分所代表的数字都要小于k，我们需要找出符合条件的分割方式数。首先我们定义一个递归函数help：
int help(char[] arr, int index, int k)
参数arr是原始字符串转化后的字符数组，index代表当前下标，k为题目给出的单个数字的最大值。返回值为从当前index到数组末尾，满足条件的分割数目。递归函内解决的问题实际上是从当前index开始找到一个大于等于1并且小于等于k的合理的数字，该数字可能由当前位（index），或者当前位与之后相邻的n位组成。因此我们需要从当前index循环至数组末尾，查看[index, i](i>=index && i<length)区间组成的数字是否小于k，如果是，代表当前区间是一个合理数字，也就是说我们在当前下标i处可以分割，接下来，我们将分割后的部分[i+1, length-1]交给子问题去解决，子问题的参数中，index等于当前i加1。其他参数保持不变。循环中，所有子问题的解相加，即是当前问题的返回值。
另外递归时，当index大于等于数组长度时，代表已经递归到数组末尾，也就是找到了一个合理的分割方式，此时返回1，这也是递归函数的一个终止条件。另外，如果当前index所指向的数字是0，这是不符合条件的（数字不能有前导0，数字0本身也不行），说明当前的分割方式不合理，返回0。
最后再考虑记忆数组（相当于动态规划解法的dp数组），使用递归方式解题的好处便是，我们可以很简单的建立记忆数组，建立记忆数组的方式是查看递归函数的参数中，有哪些是会发生变的即可，本题中，发生变的参数只有index，因此我们只需要建立一个一维数组即可。
如果你完全不懂动态规划的相关知识，或者你没能完全理解递归加记忆数组的解题方法，建议参考我之前总结过的这篇文章：LEETCODE常见算法之动态规划DP超详细白话讲解(上)
实现代码：
Integer[] memo; // 记忆数组
public int numberOfArrays(String s, int k) {
// 初始化记忆数组
memo=new Integer[s.length()];
// 递归求解
return help(s.toCharArray(),0,k);
}
// arr：原始字符串转化称为的字符数组
// index：当前下标
// 返回值：index到数组末尾区间内存在的合理方案数
int help(char[] arr, int index, int k){
// 当递归至数组末尾时，返回1
if(index==arr.length) return 1;
// 当前数字是0，不合理，返回0
if(arr[index]=='0') return 0;
// 记忆数组中存在当前值，直接返回
if(memo[index]!=null) return memo[index];
// 当前数字
long num=0;
// 返回结果
long res=0;
for(int i=index;i<arr.length;i++){
// 当前位上的数字
int n=arr[i]-'0';
// 当前数字
num = num*10+n;
// 如果当前数字大于k，不符合条件，退出循环
if(num>k) break;
// 递归求解
res+=help(arr, i+1, k);
}
memo[index]=(int)(res%1000000007);
return memo[index];
}本题解法执行时间为37ms。
Runtime: 37 ms, faster than 92.87% of Java online submissions for Restore The Array.
Memory Usage: 58 MB, less than 100.00% of Java online submissions for Restore The Array.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1416-restore-the-array-解题思路分析/