GeeksforGeeks: Dynamic Programming | Set 28 (Minimum insertions to form a palindrome)

Minimum insertions to form a palindrome
ref: http://www.geeksforgeeks.org/dynamic-programming-set-28-minimum-insertions-to-form-a-palindrome/
假设有minInsert(int begin, int end), s为string，返回 s[begin : end]所需的最少insertion
如果s[begin] == s[end], minInsert(begin, end) = minInsert(begin + 1, end - 1);
如果s[begin] != s[end], minInsert(begin, end) = min(minInsert(begin + 1, end), minInsert(begin, end - 1)) + 1;

以下是递归解法：

int minInsert(string s, int begin, int end) {
    if (begin == end) return 0;
    if (begin == end - 1) return (s[begin] == s[end])? 0 : 1;
    if (s[begin] == s[end]) {
        return minInsert(s,begin + 1,end - 1);
    }
    return 1 + min(minInsert(s,begin + 1,end),minInsert(s,begin,end - 1));
}

显而易见，有重复的子问题，所以可以用dp来解决

int minInsert(string s) {
    int n = s.length();
    vector<vector<int>> dp(n,vector<int>(n,0));
    for (int gap = 1; gap < n; gap++) {
        for (int begin = 0, end = gap; end < n; begin++,end++) {
            if (s[begin] == s[end]) {
                dp[begin][end] = dp[begin + 1][end - 1];    
            }else {
                dp[begin][end] = min(dp[begin + 1][end],dp[begin][end - 1]) + 1;    
            }
        }
    }
    
    return dp[0][n - 1];
}