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]; }
No comments:
Post a Comment