Recently I am trying to solve this problem.But i have to explicitly iterate over n-digit number.This is not exactly what we do in digit dp.Please anyone tell me how to get rid of explicit iteration. Is there any error in this code? Please Help...
Thanks in advance.
#include<bits/stdc++.h>
using namespace std;
long long solve(string s) {
int n = s.length();
long long dp[20][2][11];
memset(dp, 0 LL, sizeof(dp));
dp[0][1][0] = 1;
int ans = 0;
for (int i = 0; i < n; i++) {
for (int t = 0; t < 2; t++) {
int d = ((t == 0) ? 9 : (int) s[i] - '0');
for (int digit = 0; digit <= d; digit++) {
int l = (t && (digit == (int)(s[i] - '0')));
for (int p = 0; p <= 9; p++) {
ans += dp[i][t][p];
if (p == digit) {
// ans += dp[i][t][p];
continue;
}
dp[i + 1][l][digit] += dp[i][t][p];
}
}
}
}
long long sum = 0;
for (int i = 0; i <= 9; i++)
sum += (dp[n][1][i] + dp[n][0][i]);
return sum;
}
int main() {
string a;
cin >> a;
a = to_string(stoll(a) - 1);
long long res_a = 0;
string tt = "";
if (stoll(a) >= 0) {
for (int i = 1; i < a.length(); i++) {
tt += '9';
res_a += solve(tt);
}
res_a += solve(a);
} else res_a = -1;
string b;
cin >> b;
long long res_b = 0;
tt = "";
for (int i = 1; i < b.length(); i++) {
tt += '9';
res_b += solve(tt);
}
res_b += solve(b);
cout << res_b - res_a << endl;
}
