problem link : http://www.spoj.com/problems/MBALL/
my solution :
#include <iostream>
#include <memory.h>
using namespace std;
long long dp[100002][6];
long long solve(long long b,long long c){
if(b==0)
return 1;
if(b<0||c==5)
return 0;
if(dp[b][c]!=-1){
return dp[b][c];
}
long long ret = 0;
if(c<=0){
for(long long i=2;i<=b;i+=2)
ret += solve(b-i,1);
}
if(c<=1){
for(long long i=3;i<=b;i+=3)
ret += solve(b-i,2);
}
if(c<=2){
for(long long i=6;i<=b;i+=6){
ret += solve(b-i,3);
}
}
if(c<=3){
for(long long i=7;i<=b;i+=7){
ret += solve(b-i,4);
}
}
if(c<=4){
for(long long i=8;i<=b;i+=8){
ret += solve(b-i,5);
}
}
return dp[b][c] = ret;
}
int main()
{
int n;
cin>>n;
memset(dp,-1,sizeof(dp));
while(n--){
int s;
cin>>s;
cout << solve(s,0) << endl;
}
return 0;
}
The code is working fine but on submitting i'm getting "time limit exceeded" error . I don't want to use iterative approach . So, how can the time limit be reduced without using iterative DP ?
It seems that the results for each state of your dp are independent of the test case, so why to clear the memoization array on each test? Fix it and your code will be much faster.
carlosvfs I have updated the code as you said but I'm still getting time limit exceeded error
Now I realize that your code has a complexity of O(S^2), so not even the interactive version of your algorithm would be enough. Try to think on a faster approach.