本文共 1755 字，大约阅读时间需要 5 分钟。

思路：

因为做了上一道Palindrome Partitioning，所以一个很简单粗暴的做法就是在上题基础上修改，然而这注定是要TLE的。因为问题的需求已经不一样了，在这道题中只问切分多少次能够产生所有子串为回文的效果。全程只需要保留一个数字即可。

想到了动态规划。

考虑了很多状态的表示法，都不怎么可行。最后想到了用一个数组cp来表示在字符串s中角标i和i之后的部分需要切cp[i-1]次。

举例来讲，“aab”的边界条件就是cp[2] = 0，因为2所在的位置是'a'(从1开始计数)。含义是a之后的部分“b”需要切0次可以产生全回文的效果。而cp[3] = -1，即b之后的部分（不含b）需要切-1次产生全回文的效果。为什么要等于-1而不是0呢，这要从本算法的工作原理讲起。。。

算法工作过程：

以“aab”为例，先看看它的所有回文串

(0,0)中间为1表示“a”是一个回文串，(0,2)为1，就表示“aab”是一个回文串。这一点在上一题中应该已经明确了。

这时候我们用一个数组cp来记录i之后的所有部分切几次能形成全回文，这就是动态规划的含义了。cp数组要比s中字符个数多一个，因此cp[0]表示从s[0]（包含）到s[2]（包含）切几次能形成全回文。如本例中cp[0]就是1，表示最少切一次。

从最后一个字符s[i]开始扫，在上表里可以查到所有以s[i]为结尾的回文串，顺便能够得到区间开始的那个字符的角标，例如对于s[2]只有区间[2,2]满足要求，可以得到这个区间起始于s[2],这时候就可以更新一次cp[2]的值。根据cp的含义，cp[2]的值应该等于cp[3]的切分次数加1，加一是因为将[2,2]和[3,X]切开用了一次。这时候可以看到为什么cp[3]要等于-1了，因为b之后已经没有字符了。

还有一点就是cp[i]可能被多个值更新，因此每次更新时取最小值。

int minCut(string s) {	int m = s.size();	if (m == 0){		return 0;	}	bool ** dp = new bool*[m];	for (int i = 0; i < m; i++){		dp[i] = new bool[m];	}	for (int i = m - 1; i >= 0; i--){		for (int j = 0; j < m; j++){			if (i>j){				dp[i][j] = false;				continue;			}			else if (i == j){				dp[i][i] = true;				continue;			}			if (j - i >= 2){//[i,j]要为回文，[i+1,j-1]必须要为回文，且i，j两个字符必须相同				dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j];			}			if (j - i == 1){				dp[i][j] = (s[i] == s[j]);			}		}	}	int* cp = new int[m+2];	for (int i = 0; i < m + 2;i++){		cp[i] = 99999999;	}	cp[m] = -1;//s串的最后一个字符，需要切-1次，之后的部分全为回文	cp[m - 1] = 0;//倒数第二个字符，需要切0次，之后的部分全为回文	for (int i = m; i >= 1;i--){		for (int j = i; j >= 1;j--){			if (dp[j-1][i-1]==true){//s[i]和s[j]之间为回文				int val = cp[i] + 1;								cp[j - 1] = val < cp[j - 1] ? val : cp[j - 1];//如果有多个值在更新cp[j-1]，取最小的			}		}	}	int result = cp[0];	for (int i = 0; i < m; i++){		delete[] dp[i];	}	delete[]dp;	delete[] cp;	return result;}