Why this DP solution is wrong?


#1

map<string,int> m;
int util(vector& A,int B,int l,int r)
{
if(B==0)
{
return 0;
}

string key = to_string(l) + " " + to_string(r);

if(m.find(key)!=m.end())
    return m[key];
int ans =  max(A[l]+util(A,B-1,l+1,r),A[r]+util(A,B-1,l,r-1));

return m[key]=ans;

}

int Solution::solve(vector &A, int B) {

return util(A,B,0,A.size()-1);

}