# C++ O(N^2) time and O(N^2) space clean DP solution with details

• Already see the similar DP solutions posted on the board, here I just add some explanation and comments.

The DP idea is to calculate min cut of string s based on its prefix substring s.subtr(0, i+1) which ends at index i. Then we scan from right end to left of s.subtr(0, i+1) to search for any palindrome substring inside it so that we can get a candidate partition cut for substring s.subtr(0, i+1). We scan every possible right end palindrome substring to get the minimum cut. Eventually, the result to return is the min cut for s.subtr(0, n) == s.

int minCut(string s) {
int n = s.length();
if (n == 0) return 0;

// minCuts[i]: result for s.substr(0, i+1)
vector<int> minCuts(n, INT_MAX);

// isPalindrome[i][j]: true if s.substr(i, j-i+1) is palindrome
vector<vector<bool>> isPalindrome(n, vector<bool>(n, false));

minCuts[0] = 0;
for (int i = 1; i < n; ++i) { // calculate minCuts[i]
for (int j = i; j >= 0; --j) {
// find each palindrome substring ending at index i
// find palindrome if two ends identical and internal is palindrome
if (s[j] == s[i] && (i-j < 2 || isPalindrome[j+1][i-1])) {
isPalindrome[j][i] = true;
// entire s.substr(0, i+1) is palindrome
if (j == 0) minCuts[i] = 0;
// update minCuts[i]
else minCuts[i] = min(minCuts[i], 1+minCuts[j-1]);
}
}
}
return minCuts[n-1];
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.