why i am getting TLE in memoization and not in top down approach of dp
noname
116
Interview

QUESTION:-https://cses.fi/problemset/task/1637

TOP DOWN

public static void process()throws IOException
{
int n=I();
int dp[]=new int[n+1+10];
for(int i=0;i<=9;i++)
{
dp[i]=1;
}
for(int i=10;i<=n;i++)
{
int min=Integer.MAX_VALUE;
int p=i;int t=i;
// pn(p);
while(t>0)
{

		    	  int o=Integer.MAX_VALUE;
		    	  if(t%10!=0)
		          o=1+dp[p-(t%10)];

		          min=Math.min(o,min);
		          t=t/10;
		      }
		     dp[i]=min;

		  }

	  pn(dp[n]);

  }

******************

MEMOIZATION

**

  public static int count(int n,int dp[])
{
    if(n<10 && n>=0)
    {
    	return 1;
    }
    else
    if(dp[n]!=Integer.MAX_VALUE)
    {
    	return dp[n];
    }
    else
    {
    	int p=n;int t=n;
    	int min=Integer.MAX_VALUE;
    	while(t>0)
    	{
    		int o=Integer.MAX_VALUE;
    		if(t%10!=0)
    		o=1+count((p-t%10),dp);
    		min=Math.min(min, o);
    		t=t/10;
    	}
    	dp[n]=min;
    	return min;
    }



}
public static void process()throws IOException
{
	int n=I();
	int dp[]=new int[n+1];
	Arrays.fill(dp,Integer.MAX_VALUE);
	pn(count(n,dp));

}
Comments (1)