How to use Dynamic Programming number of distinct function call is too large as compare to the maximum allowed size of the array

Question

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.....

Answer 1

It is better to not use moves[10000000] rather use a map. You do not need to cover all integers from 1 to 10^9, rather just use

/2 or (-1 & then /2) whichever is applicable

and (/3) or (-1 & then /3) or (-1, -1 & then /3) whichever is applicable and you will get your solution pretty fast for (t=)1000 test cases.