Jul 22, 2017 · 1 min read
This is the code using simple recursion for the above problem:
long long recurr(long long n,long long k){
if(n<=2)return 1;
return recurr(n-1,k)+k*recurr(n-2,k);
}
int main() {
long long n,k;
cin>>n>>k;
cout<<recurr(n,k);
return 0;
}
— — — — — — — — — — — — —
This is the code modified to use dynamic programming reducing the runtime to O(n)
map<int,int> m;
long long recurr(long long n,long long k){
if(n<=2)return 1;
if(m.find(n)==m.end())m[n]=recurr(n-1,k)+k*recurr(n-2,k);
return m[n];
}
int main() {
long long n,k;
cin>>n>>k;
cout<<recurr(n,k);
return 0;
}