why memoized solution fails in this problem:↵
[Source](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=653&page=show_problem&problem=1247)↵
//below is the given code↵
↵
↵
//can you help me spot some patterns to optimise it!!!↵
↵
↵
↵
lli solve(lli x,lli y,lli e,lli w)↵
{↵
if(dp[x][y]!=100000)↵
{↵
↵
return dp[x][y];↵
}↵
if((x*x+y*y)==e*e)↵
{↵
return 0; ↵
}↵
for(int i=1;i<=N;i++)↵
{↵
if(((x+coins[i].a)*(x+coins[i].a)+(y+coins[i].b)*(y+coins[i].b))<=e*e)↵
{↵
dp[x][y]=min(dp[x][y],(solve(x+coins[i].a,y+coins[i].b,e,i)+1));↵
}↵
}↵
return dp[x][y];↵
}↵
↵
int main()↵
{↵
↵
cin>>n;↵
↵
for(int i=1;i<=n;i++)↵
{↵
↵
f=0;↵
↵
for(int j=0;j<1001;j++)↵
{↵
for(int k=0;k<1001;k++)↵
dp[j][k]=100000;↵
}↵
↵
for(int i=0;i<100000;i++)↵
dp1[i]=100000;↵
cin>>N>>e;↵
↵
for(int j=1;j<=N;j++)↵
{↵
cin>>x>>y;↵
coins[j].a=x;↵
coins[j].b=y;↵
}↵
lli d=solve(0,0,e,0);↵
if(d==100000)↵
cout<<"not possible"<<endl;↵
else↵
cout<<d<<endl;↵
}↵
}
[Source](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=653&page=show_problem&problem=1247)↵
//below is the given code↵
↵
↵
//can you help me spot some patterns to optimise it!!!↵
↵
↵
↵
lli solve(lli x,lli y,lli e,lli w)↵
{↵
if(dp[x][y]!=100000)↵
{↵
↵
return dp[x][y];↵
}↵
if((x*x+y*y)==e*e)↵
{↵
return 0; ↵
}↵
for(int i=1;i<=N;i++)↵
{↵
if(((x+coins[i].a)*(x+coins[i].a)+(y+coins[i].b)*(y+coins[i].b))<=e*e)↵
{↵
dp[x][y]=min(dp[x][y],(solve(x+coins[i].a,y+coins[i].b,e,i)+1));↵
}↵
}↵
return dp[x][y];↵
}↵
↵
int main()↵
{↵
↵
cin>>n;↵
↵
for(int i=1;i<=n;i++)↵
{↵
↵
f=0;↵
↵
for(int j=0;j<1001;j++)↵
{↵
for(int k=0;k<1001;k++)↵
dp[j][k]=100000;↵
}↵
↵
for(int i=0;i<100000;i++)↵
dp1[i]=100000;↵
cin>>N>>e;↵
↵
for(int j=1;j<=N;j++)↵
{↵
cin>>x>>y;↵
coins[j].a=x;↵
coins[j].b=y;↵
}↵
lli d=solve(0,0,e,0);↵
if(d==100000)↵
cout<<"not possible"<<endl;↵
else↵
cout<<d<<endl;↵
}↵
}
