#include <stdio.h>
#define gc getchar
int read_int()
{
char c = gc();
while(c<‘0’ || c>‘9’)
c = gc();
int ret = 0;
while(c>=‘0’ && c<=‘9’)
{
ret = 10 * ret + c - ‘0’;
c = gc();
}
return ret;
}
int solve(int i,int j,int n,int a[][n])
{
int t1,t2,t,temp;
temp=i*j;
int cache[5050]={0};
if(i>n-1)
return 0;
else if(cache[temp]!=0)
return (cache[i*j]);
t1=solve(i+1,j,n,a);
t2=solve(i+1,j+1,n,a);
if(t1>=t2)
t=t1+a[i][j];
else
t=t2+a[i][j];
cache[temp]=t;
return t;
}
int main()
{
int t,n,i,j,res;
t=read_int();
while(t!=0)
{
n=read_int();
int a[n][n];
for(i=0;i<n;i++)
{
for(j=0;j<=i;j++)
{
a[i][j]=read_int();
}
}
res=solve(0,0,n,a);
printf("%d\n",res);
t–;
}
return 0;
}
Someone please help me optimise this code I have used memoization still i am getting time limit exceeded for this code.It gives the output correct,just cant get to optimise it further.