Can someone explain how this dp solution work for this problem in an editorial type manner?
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sp ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define cps CLOCKS_PER_SEC
#define mod (long long)1000000007
#define f first
#define s second
#define debug1(x) cout<<x<<"\n"
#define debug2(x,y) cout<<x<<" "<<y<<"\n"
#define debug3(x,y,z) cout<<x<<" "<<y<<" "<<z<<"\n"
#define nl cout<<"\n";
#define pq priority_queue
#define inf 0x3f3f3f3f
#define test cout<<"abcd\n";
#define pi pair<int,int>
#define pii pair<int,pi>
#define pb push_back
#define mxn 200005
vector<int> dig(int n){
vector<int> v;
while(n){
v.push_back(n % 10);
n /= 10;
}
return v;
}
int dp[19][11][11];
vector<int> digit;
int K;
int solve(int id, int prev, int y){
if(id < 0)
return (prev != 10);
auto &ans = dp[id][prev][y];
if(ans != -1)
return ans;
ans = 0;
int k = y ? digit[id] : 9;
for(int i = 0; i <= k; ++i){
int ny = (digit[id] == i) ? y : 0;
if(i == 0 && prev == 10)
ans += solve(id - 1, 10, ny);
else if(prev == 10)
ans += solve(id - 1, i, ny);
else if(abs(prev - i) <= K)
ans += solve(id - 1, i, ny);
}
return ans;
}
int calc(int x){
memset(dp,-1,sizeof dp);
digit.clear();
digit = dig(x);
return solve(digit.size()-1, 10, 1);
}
int32_t main(){
sp;
int t;
cin>>t;
while(t--){
int a, b;
cin>>a>>b>>K;
cout<<calc(b) - calc(a-1)<<"\n";
}
return 0;
}
Problem Link: CodeChef: Practical coding for everyone