我给一些编程大赛..............，我已经解决了相关的动态programming.Below一个问题是这个问题的链接

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链接

我已经给该问题的解决方案如下： - ：

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;
}

在上述溶液中，我已采取的阵列移动[]。此数组将保持subproblem.In的FindMove函数的结果，如果该问题的大小是小的，这将存储在子问题maves的结果阵列和回报。

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.

如果子问题的规模大，那么我已经调用的函数FindMoves（）三次（一个用于强度-1，第二个用于强度/ 2，如果能被2整除和3三分之一强/ 3，如果整除）和最后取最小值出三种。

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.

以上的解决方案工作正常，当问题的大小与数组的大小（1-10 ^ 6），但不工作的规模大于10 ^ 6，因为我的数组大小为10 ^ 6。

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.

以上解决方案时，输入的尺寸太大，不工作（在这个问题强度在1到10 ^ 9），但我的数组大小比小。（我受不了了，因为如果我需要更多的我收到内存超出错误）

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.$c$cchef.com/wiki/教程动态编程

我的问题是只有我使用动态规划（递归），当问题的规模过大，我的解决办法是行不通的，因为我的数组大小没有太多大

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

请建议我该怎么办...... 任何帮助将是AP preciated .....

Please suggest me what to do...... Any help would be appreciated.....

推荐答案

这是更好地不使用移动[千万]而使用的地图。你并不需要覆盖所有整数从1到10 ^ 9，而只是使用

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或（-1＆安培;然后/ 2）取适用

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

和（/ 3）或（-1放大器;然后/ 3）或（-1，-1放大器;然后/ 3），以适用者为准，你会得到你的解决方案pretty的快（T =） 1000个测试用例。

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.