在C ++中还原阵列
给定字符串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]
为了解决这个问题，我们将遵循以下步骤-
constintm=1e9+7
定义一张映射dp
定义一个函数add()，这将需要a，b，
return（（amodm）+（bmodm））modm
定义一个函数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：=tempasnumber
如果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