I Have Tried the following problem using Digit DP please tell me how to apply memoization to it
Your code here...
#include<iostream>
#include<vector>
#define Mod 1000000007
#define ll long long
using namespace std;
int a,b,n;
bool check_good(int digit_sum){
bool res=1;
while(digit_sum>0){
if(digit_sum%10!=a && digit_sum%10!=b){
res=0;
break;
}
digit_sum/=10;
}
return res;
}
vector<int > num;
ll call(int pos,int digit_sum){
if(pos==n){
if(check_good(digit_sum)){
return 1;
}
else{
return 0;
}
}
ll ans=0;
ans=(ans+call(pos+1,digit_sum+a))%Mod;
ans=(ans+call(pos+1,digit_sum+b))%Mod;
return ans;
}
int main(){
cin>>a>>b>>n;
cout<<call(0,0);
return 0;
}
public void run() { InputReader sc = new InputReader(System.in); //Scanner sc=new Scanner(System.in); // Random sc=new Random(); PrintWriter out = new PrintWriter(System.out);
Thanks for combinatorics solution !! So Shall I assume that this problem couldn't be solved using DigitDP ? and combinatorics is the only way to solve it
you can use HashMap in java but it takes O(n*MAX_SUM) and it will time out