Chiranjeev Thomas
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;
}

)