Easy Memoization


#1

int MOD=1000000007;

int func(vector& arr, int sum, int k, vector<vector>& t){

if(sum==0 && k==0){
return 1;}

if(sum<0)
return 0;

if(k==0)
return 0;

if(t[sum][k]!=-1)
return t[sum][k];


int ans=0;
for(int i=0;i<arr.size();i++){
    
    if(arr[i]<=sum)
    ans= ((ans%MOD)+(func(arr,sum-arr[i],k-1,t)%MOD))%MOD;
    
}

return t[sum][k]= ans%MOD;

}

int Solution::solve(int A, int B) {

vector<vector<int>> t(1000, vector<int>(1000,-1));

vector<int> arr= {1,2,3,4,5,6,7,8,9,0};

int ans=0;

for(int i=0;i<9;i++){
    ans= ((ans%MOD) + (func(arr,B-arr[i],A-1,t)%MOD))%MOD;
}

return ans%MOD;

}