假设有一个用于打印数组A的数组元素的程序，但是该程序中存在一些错误。在该程序中，每个元素后面没有空格，因此，如果我们有一个打印的字符串，是否可以再次重新生成数组？我们知道数组元素的范围是1到k。
给定字符串s和整数k。我们必须找到多少种方法可以还原数组。答案可能非常大，因此以10 ^ 9 + 7为模返回。
因此，如果输入像S =“ 1318”并且k = 2000，那么输出将是8，因为我们可以形成8个不同的数组，例如[1318]，[131,8]，[13,18]，[1,318 ]，[1,3,18]，[1,31,8]，[13,1,8]，[1,3,1,8]
为了解决这个问题，我们将遵循以下步骤-
const int m = 1e9 + 7
定义一张映射dp
定义一个函数add()，这将需要a，b，
return（（a mod m）+（b mod m））mod m
定义一个函数help()，它将使用idx，s，num，k，
如果idx> = s的大小，则-
返回1
如果idx在dp中，而num在dp [idx]中，则-
返回dp [idx，num]
ret：= 0
如果num> = 1且num> = k并且s [idx]不等于'0'，则-
ret：=添加（帮助(idx,s,0,k)，ret）
如果num * 10 +（s [idx]-'0'）<= k，则-
ret：= add（help（idx + 1，s，num * 10 +（s [idx]-ASCII'0'），k），ret）
dp [idx，num]：= ret
返回ret
从主要方法中执行以下操作-
n：= s的大小
定义大小为n + 1的数组ans
ans [0]：= 1
s：=在s之前连接一个空格
ks：=将k转换为字符串
对于初始化i：= 1，当i <= n时，更新（将i增加1），-
温度：= s [j] +温度
如果s [j]与'0'相同，则-
如果temp的大小> ks的大小，则-
val：= temp as number
如果val> = 1且val <= k，则-
忽略以下部分，跳至下一个迭代
从循环中出来
ans [i]：= add（ans [i]，ans [j-1]）
中位数：= 1
temp：=空字符串
对于初始化j：= i，当j> = 1且cnt <= 10时，更新（将j减1），（将cnt加1），-
返回ans [n]
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int m = 1e9 + 7;
class Solution {
public:
unordered_map<int, unordered_map<lli, int> > dp;
lli add(lli a, lli b){
return ((a % m) + (b % m)) % m;
}
int help(int idx, string& s, lli num, int k){
if (idx >= s.size())
return 1;
if (dp.count(idx) && dp[idx].count(num))
return dp[idx][num];
int ret = 0;
if (num >= 1 && num <= k && s[idx] != '0') {
ret = add(help(idx, s, 0, k), ret);
}
if (num * 10 + (s[idx] - '0') <= k) {
ret = add(help(idx + 1, s, num * 10 + (s[idx] - '0'), k),
ret);
}
return dp[idx][num] = ret;
}
int numberOfArrays(string s, int k){
int n = s.size();
vector<lli> ans(n + 1);
ans[0] = 1;
s = " " + s;
string ks = to_string(k);
for (lli i = 1; i <= n; i++) {
lli cnt = 1;
string temp = "";
for (lli j = i; j >= 1 && cnt <= 10; j--, cnt++) {
temp = s[j] + temp;
if (s[j] == '0')
continue;
if (temp.size() > ks.size())
break;
lli val = stol(temp);
if (val >= 1 && val <= k) {
ans[i] = add(ans[i], ans[j - 1]);
}
}
}
return ans[n];
}
};
main(){
Solution ob;
cout << (ob.numberOfArrays("1318",2000));
}"1318", 2000
输出结果
8