一开始还用上一题的方法一定超时了，没想到，dp还是难，要2刷和理解 Calculate and maintain 2 DP states: 1. pal[i][j] , which is whether s[i..j] forms a pal 2. 3. d[i], which is the minCut for s[i..n-1] 4. Once we comes to a pal[i][j]==true: • if j==n-1, the string s[i..n-1] is a Pal, minCut is 0, d[i]=0; • else: the current cut num (first cut s[i..j] and then cut the rest s[j+1…n-1]) is 1+d[j+1], compare it to the exisiting minCut num d[i], repalce if smaller. d[0] is the answer.
class Solution {public: int minCut(string s) { int n = s.length(); if(n == 0) return 0; vector<vector<bool>>v(n, vector<bool>(n, false)); vector<int>dp(n); for(int i = n - 1; i >= 0; -- i){ dp[i] = n - i - 1; for(int j = i; j < n; ++ j){ if(s[i] == s[j] && (j - i < 2 || v[i + 1][j - 1] == true)){ v[i][j] = true; if(j == n - 1) dp[i] = 0; else if(dp[j + 1] + 1 < dp[i]) dp[i] = dp[j + 1] + 1; } } } return dp[0]; }};新闻热点
疑难解答
