I was giving some programming contest.............. and I have solved one problem related to the dynamic programming.Below is the link of the problem
Prblem link
I have given the solution of the problem as follows-:
#include<stdio.h>
short int moves[10000000];
int minimum(int a ,int b, int c)
{
if(a<b)
if(a<c)
return a;
else
return c;
else
if(b<c)
return b;
else
return c;
}
int FindMoves(int strength)
{
int m1=0,m2=0,m3=0;
int isBy2=0,isBy3=0;
if(strength==1)
{
moves[1]=0;
return 0;
}
else if(strength==2)
{
moves[2]=1;
return 1;
}
else if(strength==3)
{
moves[3]=1;
return 1;
}
else if(strength==4)
{
moves[4]=2;
return 2;
}
else if(strength==5)
{
moves[5]=3;
return 3;
}
else
{
if(moves[strength-1]!=-1)
{
m1=moves[strength-1];
}
else
{
m1=FindMoves(strength-1)+1;
moves[strength-1]=m1;
}
if(strength%2==0)
{
isBy2=1;
if(moves[strength/2]!=-1)
{
m2=moves[strength/2];
}
else
{
m2=FindMoves(strength/2)+1;
moves[strength/2]=m2;
}
}
if(strength%3==0)
{
isBy3=1;
if(moves[strength/3]!=-1)
{
m3=moves[strength/3];
}
else
{
m3=FindMoves(strength/3)+1;
moves[strength/3]=m3;
}
}
if(isBy2 && isBy3)
{
return minimum(m1,m2,m3);
}
else if(isBy3)
{
if(m1<m3)
return m1;
else
return m3;
}
else if(isBy2)
{
if(m1<m2)
return m1;
else
return m2;
}
else
{
return m1;
}
}
}
int main()
{
int i,t;
int result;
unsigned long int a[1000];
scanf("%d",&t);
for(i=0;i<t;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<1000000;i++)
{
moves[i]=-1;
}
for(i=0;i<t;i++)
{
result = FindMoves(a[i]);
printf("%d\n",result);
}
return 0;
}
In the above solution, I have taken an array moves[].This array will keep the result of the subproblem.In the FindMove function, if size of the problem is small, it would store the result of that subproblem in maves array and return.
If size of the subproblem is large, then I have called the function FindMoves() three times(one for strength-1,second for strength/2 if divisible by 2 and third by strength/3 if divisible by 3) and finally taking the minimum out of three.
Above solution is working fine when the size of the problem is with in the array size(1-10^6) but not working for size greater than 10^6 because my array size is 10^6.
Above solution is not working when the size of the input is too large(In the problem strength is between 1 to 10^9) but my array size is smaller than that.(I can not take more because If I take more I am receiving Memory exceeding error)
If you are not getting my problem, the same problem is available here.
http://www.codechef.com/wiki/tutorial-dynamic-programming
My problem is only that I am using dynamic programming(with recursion) and when size of the problem is too large, my solution is not working because my array size is not too much large
Please suggest me what to do...... Any help would be appreciated.....
