首页 > 代码库 > LeetCode "Palindrome Partition II" - Double DP
LeetCode "Palindrome Partition II" - Double DP
A so juicy and interesting problem! Recommend to everyone!
A final solution may not jump into your mind immediately, of course, DP is not a trivial topic. So let‘s go step by step - it is more interesting that how you get to destination than destination itself!
Since it is palindrome, so we need to know all palindromes - to avoid duplicated calculation, we need DP.
We made a step further but there‘s still a gap between us and AC: the min cut. "Minimum, maximum, shortest, longest.." etc. It means DP. So, we need a second DP. Since it is a linear value space, an ideal DP would be 1D - and we can. It is all matter of scanning. If s[0..i] is not palindrome, we pick min(dp2[j] + 1, when s[j+1..i] is palindrome). And you can get AC then :)
Reference: http://yucoding.blogspot.com/2013/08/leetcode-question-133-palindrome.html
class Solution {public: int minCut(string s) { size_t len = s.length(); if (len <= 1) return 0; // Init vector<vector<bool>> dp; dp.resize(len); for (int i = 0; i < len; i++) { dp[i].resize(len); std::fill(dp[i].begin(), dp[i].end(), false); dp[i][i] = true; } // Go DP 1 - all palindromes int min = std::numeric_limits<int>::max(); for (size_t ilen = 2; ilen <= len; ilen += 1) // current substr len for (size_t i = 0; i <= len - ilen; i ++) // current starting inx { char c0 = s[i]; char c1 = s[i + ilen - 1]; bool bEq = c0 == c1; if (ilen == 2) dp[i][i + 1] = bEq; else dp[i][i + ilen - 1] = bEq && dp[i + 1][i + ilen - 2]; } vector<int> dp2; dp2.resize(len); std::fill(dp2.begin(), dp2.end(), 0); // Go DP 2 dp2[0] = 0; for (int i = 1; i < len; i++) { if (dp[0][i]) dp2[i] = 0; // palin already? else { // find min num of palin int min = len; for (int j = 0; j < i; j++) if (dp[j + 1][i]) { min = std::min(min, dp2[j] + 1); } dp2[i] = min; } } return dp2[len - 1]; }};