Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
问题：对给定的字符串进行分割，使得每个子字符串都是回文的。求最小的分割情况。
假设将 s 分割为两段，[0, i-1], [i, n-1]，若 [0, i-1] 为回文字符串，则 ( [i, n-1] 的最小分割次数字符串数 + 1 ) 便是 s 以 i 为分割点最小分割情况的子字符串数。
将 i 从 1 到 n-1 遍历一边，便得到 s 依次以 i 为分割点得最小分割情况的子字符串数，其中最小的便是原问题的解。
利用 DP 思路，存储中间结构，避免重复的计算。 tailMinCutSC[i] 表示从 下标i 到结尾的最小分割情况的子字符串数。
算法思路是正确的，但是扔到 LeetCode 却超时了。接下来进行多次优化：
1. 求解子问题时，将 substr 的操作改为了 传引用 & 和 下标来表示，优化效果不明显。仅从 1204 ms 加快到 936 ms 。
2. 求解 s[i, j] 是否是回文时，每次从 i 到 j 扫一遍，耗时太长。采用二维数组 PalinVV 记录全部可能的结果，减低时间复杂度。优化前的耗时我不太会分析，通过程序记录开看，是远远超过 O(n*n)的，进行这步优化后，使得整个算法时间复杂降为 O(n*n)。
3. 实现第2 步优化，本身也是一个 DP 思路。PalinVV[i][k](i <= k)，表示 s[i,k] 是否是回文，可以根据 PalinVV[i+1][k-1] 结果快速得到。对于 PalinVV 二维表格，从下往上计算，方便利用之前的结果。
vector<int> tailMinCutSC; const int NEWONE = -; vector<vector<bool>> PalinVV; /**
* 判断字符串 s 的[sIdx, eIdx] 部分字符是否是回文字符串。
*
*/
bool isPalindrome(const string& s, int sIdx, int eIdx){ return PalinVV[sIdx][eIdx];
} /**
* 判断字符串 s 的[sIdx, eIdx] 部分字符是否是回文字符串。
*
*/
bool isPalindrome(const string& s, int sIdx){ return isPalindrome(s, sIdx, (int)s.size()-);
} /**
* 对 s 字符串 [sIdx, n]部分进行回文分割，返回最小分割情况的子字符串数。
*
*/
int palindromeCut(const string& s, int sIdx){ if (isPalindrome(s, sIdx)) { tailMinCutSC[sIdx] = ;
return ;
} int minCutSC = (int)s.size() - sIdx; for (int i = sIdx + ; i < s.size(); i++) {
bool leftP = isPalindrome(s, sIdx, i-);
if (leftP == false) {
continue;
}
int rightSC;
if (tailMinCutSC[i] != NEWONE) {
rightSC = tailMinCutSC[i];
}else{
rightSC = palindromeCut(s, i);
tailMinCutSC[i] = rightSC;
} int oneSolution = rightSC + ;
minCutSC = min(minCutSC, oneSolution); } return minCutSC;
} /**
* 求字符串 s 的任意子字符串是否是回文，结果存于二维布尔数组
* 求解全部可能的子字符串，符合 overlapping & optimal subcontructure，可以采用 DP 思想加速求解。
*
*/
void calculatePalinVV(string& s){ vector<vector<bool>> vvtmp(s.size(), vector<bool>(s.size())); PalinVV = vvtmp; for (int i = (int)s.size()-; i >= ; i--) {
PalinVV[i][i] = ;
} for (int i = (int)s.size()-; i >= ; i--) {
if (s[i] == s[i+]) {
PalinVV[i][i+] = ;
}else{
PalinVV[i][i+] = ;
}
} for (int i = (int)s.size()-; i >= ; i--) {
for (int k = (int)s.size()-; k >= i + ; k--) {
if (s[i] == s[k] && PalinVV[i+][k-]) {
PalinVV[i][k] = ;
}else{
PalinVV[i][k] = ;
}
}
}
} int minCut(string s) { calculatePalinVV(s); vector<int> tmp(s.size(), NEWONE);
tailMinCutSC = tmp; int minSC = palindromeCut(s, ); tailMinCutSC[] = minSC; int minCutPoint = minSC - ; return minCutPoint;
}
参考资料 :