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);elsereturn 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";}}