im trying to use dynamic programming in solving this problem but i got TLE . can someone give me hint?
#include
#include
#include <bits/stdc++.h>
using namespace std;
#define endl ‘\n’;
const int MXSIZE = 1e6+6;
int recur(int k, vectorbe , vectorce, int n,int r[]){
int ai=0;
if(r[n]>=0){
return r[n];
}
if(n<=k){
return be[n];
}
for(int i=0;i<n;i++){
ai=ai+ce[i]*recur(k,be,ce,n-i-1,r);
}
r[n]=ai;
return ai;
}
int main(){
int k,b,c,n,total;
cin>>total;
vectorbe;
vectorce;
for(int i=1;i<=total;i++){
be.clear();
ce.clear();
cin>>k;
int copyk=k;
int copyk2=k;
while(copyk–){
cin>>b;
be.push_back(b);
}
while(copyk2–){
cin>>c;
ce.push_back©;
}
cin>>n;
int r[n];
for(int i=0;i<n;i++){
r[i]=-100;
}
int hasil=recur(k-1,be,ce,n-1,r);
int mod=hasil % 1000000000;
cout<<mod<<endl;
}
}
