Form a palindrome

Given a string, find the minimum number of characters to be inserted to convert it to palindrome.

For Example:

• ab: Number of insertions required is 1. bab or aba
• aa: Number of insertions required is 0. aa
• abcd: Number of insertions required is 3. dcbabcd

• Time : O(n^2)
• Space : O(n^2)

class Solution{
    int dp[1001][1001];
    int helper(string& s, int l, int r) {
        if(l > r) return 0;
        if(l == r) return 1;
        if(dp[l][r] != -1) return dp[l][r];
        int& res = dp[l][r] = 0;
        res = max(res, helper(s,l+1,r));
        res = max(res, helper(s,l,r-1));
        if(s[l] == s[r])
            res = max(res, 2 + helper(s,l+1,r-1));
        return res;
    }
public:
    int countMin(string str){
        int n = str.length();
        memset(dp, -1, sizeof dp);
        return n - helper(str, 0, n - 1);
    }
};