This problem has really annoyed me. Its a simple dp, If I do not memoize it I am getting correct answer for the test cases. If I memoize, I am getting 1 greater than the actual answer for the last couple of test cases. Any help appreciated. There are several solutions to this problem already available. I do not want to refer those because first time I am so close. How can memoization change the answer. I am baffled. Thanks for your time.

This is my code with memoization:

#include<iostream>
using namespace std;
 
string a;
int n;
int dp[1005][1005];
 
int solve(int i, int j, int moves)
{
	if(i>=j)
		return dp[i][j] =  moves;
	
	if(dp[i][j]!=INT_MAX)
		return dp[i][j];
 
	if(a[i]==a[j])
		return dp[i][j] = solve(i+1, j-1, moves);
	else
		return dp[i][j] = min(min(solve(i+1, j-1, moves+1), solve(i+1, j, moves+1)), solve(i, j-1, moves+1));
}
 
 
 
 
int main()
{
	int T;
	cin >> T;
	while(T--)
	{
		cin >> a;
		n = a.length();
		for(int i=0;i<1005;i++)
			for(int j=0;j<1005;j++)
				dp[i][j] = INT_MAX;
 
		int ans = solve(0, n-1, 0);
 
		cout << ans << "\n";
	}
}