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 ?
