132. Palindrome Partitioning II

We need to maintain two DP states:
1. palindrome[i][j], which means if s[i, j] is a palindrome.
2. dp[i], which means minimum cuts for s[i, n-1].

First of all, dp[i] will be initialized to n-1-i as if there is no palindrome in s[i, n-1], we need to cut at every character.

Then, we need to scan from i to n-1 and see if any palindrome exists before, i.e. s[i] == s[j] and palindrome[i+1][j-1] is true. If we find the palindrome at the end, i.e. j == n-1, we don't need to cut, i.e. d[i] = 0, else if we find the palindrome at j, then we need to cut at j, i.e. we have substring s[i, j] and s[j+1, n-1]. Therefore, to get the minimum cut at i, we just need to get the min(d[i], d[j+1]+1). Also, don't forget to make palindrome[i][j] true.

1:  class Solution {  
2:  public:  
3:    int minCut(string s) {  
4:      int n = s.size();  
5:      vector<vector<bool>> palindrome(n, vector<bool>(n, false));  
6:      vector<int> dp(n, 0);  
7:      for (int i = n-1; i >= 0; i--) {  
8:        dp[i] = n-1-i;  
9:        for (int j = i; j < n; j++) {  
10:          if (s[i] == s[j] && (j-i<2 || palindrome[i+1][j-1] == true)) {  
11:            palindrome[i][j] = true;  
12:            if (j == n-1) dp[i] = 0;  
13:            else dp[i] = min(dp[i], 1+dp[j+1]);  
14:          }  
15:        }  
16:      }  
17:      return dp[0];  
18:    }  
19:  };