MINIMUM NUMBER OS STEPS SPOJ TLE

general
1

LINK TO QUESTION - > http://www.spoj.com/problems/MST1/

#include<cstdio>
#define M 20000007
typedef int ull;


inline ull mi(ull a,ull b)
{  
   if(a>b)
    return b;
else
    return a;
}
int main()
{

int t;
scanf("%d",&t);
while(t--)
{
    ull n;
    scanf("%d",&n);
    ull *dp=new ull[n+1];
    dp[1]=0;
    for(ull i=2;i<=n;i++)
    {

        dp[i]=dp[i-1]+1;
        if(i%2==0)
        {
            dp[i]=mi(dp[i],1+dp[i/2]);
        }

        if(i%3==0)
        {
            dp[i]=mi(dp[i],1+dp[i/3]);
        }
    }
    printf("%d\n",dp[n]);

}
return 0;
}

here is my solution
i am using dp to solve this
still getting tle
can you please tell me what should be done to optimize this code

2

Why are you calculating the values repeatedly? For every input value of n, you are traversing the loop 2 to n. Lets say first input was 7. In the first iteration(corresponding to test cases), you find values of all dp[1…7]. Next input was lets say, 15, so you are again calculating dp[1…15] where dp[1…7] was already there. Why do this repetitive work? Pre-calculate the values for all i belonging to set [1,MAX] where MAX is 20000000. Now, for every value of n, just output dp[n], so, constant time. Computation time(Processing time is O(n)).

Refer my solution here or on the same post on quora you A2A. :stuck_out_tongue: