【LeetCode: 1416. 恢复数组 | 暴力递归=＞记忆化搜索=＞动态规划 】

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨
🌲 作者简介：硕风和炜，CSDN-Java领域新星创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯

🚗 知识回顾

该题和我们之前的题目在求解的思路上相似之处，感兴趣的同学可以学习一下相关的内容。

• 【LeetCode: 1043. 分隔数组以得到最大和 | 暴力递归=＞记忆化搜索=＞动态规划 | 线性dp & 区间dp】
• 【LeetCode: 2369. 检查数组是否存在有效划分 | 暴力递归=＞记忆化搜索=＞动态规划 | 线性dp】
• 【LeetCode: 1105. 填充书架 | 暴力递归=＞记忆化搜索=＞动态规划 | 线性dp & 业务限制】

🚩 题目链接

• 1416. 恢复数组

⛲ 题目描述

某个程序本来应该输出一个整数数组。但是这个程序忘记输出空格了以致输出了一个数字字符串，我们所知道的信息只有：数组中所有整数都在 [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进行一个划分，每一个划分的部分都小于等于k的总体方案数。
2. 总体求解思路还是动态规划，为什么呢？因为我们想要求解的是从0位置开始，到s的最后一个位置结束，满足每个部分小于等于k的总体方案数目。如果说我们此时划分了0-cur位置，那么从cur-最后一个结束位置还需要重复这个过程，所以说，该过程是存在重复子问题的，我们可以通过动态规划来进行一个求解。
3. 首先，我们还是设计一个递归函数，递归函数的含义是从index位置开始进行划分，找到所有满足的方案数。

🥦 实现代码

class Solution {private int mod=(int) 1e9 + 7;public int numberOfArrays(String s, int k) {return (int)(process(0,s,k)%mod);}public long process(int index,String s,int k){if(index>=s.length()){return 1;}long res=0;for(int i=index;i<s.length();i++){long sum=0;for(int j=index;j<i+1;j++){sum=sum*10+s.charAt(j)-'0';}if(s.substring(index,i+1).charAt(0)!='0'&&sum<=k&&sum>=1){res+=process(i+1,s,k)%mod;}}return res%mod;}
}

🥦 运行结果

时间超限了，不要紧哦，我还有锦囊妙计！

⚡ 记忆化搜索

🥦 求解思路

1. 根据我们递归的分析，在递归的过程中会产生重复的子过程，所以我们想到了加一个缓存表，也就是我们的记忆化搜索。
2. 因为题目给定我们的k的限制条件是k≤10^9 ，所以我们最多只要枚举 10个数字就行了，这个也是我们优化的一个点，否则时间还是会超限的。

🥦 实现代码

class Solution {private int mod=(int) 1e9 + 7;private long[] dp;public int numberOfArrays(String s, int k) {dp=new long[s.length()];Arrays.fill(dp,-1);return process(0,s,k)%mod;}public int process(int index,String s,int k){if(index>=s.length()){return 1;}if(dp[index]!=-1) return (int)(dp[index]);long res=0;long sum=0,base=10;for(int i=index;i<s.length()&&i-index<=10;i++){if(s.substring(index,i+1).charAt(0)=='0') continue;sum=sum*base+s.charAt(i)-'0';if(sum<=k&&sum>=1){res+=process(i+1,s,k)%mod;}}return (int)(dp[index]=res%mod);}
}

🥦 运行结果

⚡ 动态规划

🥦 求解思路

1. 按照我们之前递归和记忆化搜索的思路，通过动态规划实现出来。

🥦 实现代码

class Solution {private int mod=(int) 1e9 + 7;private long[] dp;public int numberOfArrays(String s, int k) {int n=s.length();dp=new long[n+1];dp[n]=1;for(int index=n-1;index>=0;index--){long res=0;long sum=0,base=10;for(int i=index;i<s.length()&&i-index<=10;i++){if(s.substring(index,i+1).charAt(0)=='0') continue;sum=sum*base+s.charAt(i)-'0';if(sum<=k&&sum>=1){res+=dp[i+1]%mod;}}dp[index]=res%mod;}return (int)(dp[0]%mod);}
}

🥦 运行结果

💬 共勉