题目和上题一样 leetcode Palindrome Partitioning ，这里需要求的是最小的分割数，也就是上一题的所有可能里面最少的一个分割。例如：
For example, given
s
=
"aab"
,
Return
1
since the palindrome partitioning
["aa","b"]
could be produced using 1 cut.
很明显，如果我们和上体一样把所有的答案求出来，然后返回最少元素的长度-1就可以了，但是Memory Limited了。我以为是ans存不了那么多的分割可能，所有每次只判断要存的是否比之前的短，短的才需要存。这时候变成Time Limited了，还是不行。
只能用DP了。先用DP求i到j是否可能为回文。判断i到j是回文有两种情况：
1.如果i到j的长度为1，也就是j-i=0那肯定就是回文了，如果长度为2并且s[i] == s[j]那也是回文。长度为其他的就用下一点判断了
2.i到j是回文，那么i+1到j-1是回文，并且s[i] == s[j]。
所以可以用第1点初始化，然后利用第2点扩展所有。或者可以说为了能够使用第2点dp求解，第1点是必须的。然后i从末尾开始，j从i开始，这样每次需要第2点的时候第一点都已经做完了。所以初始化可以一起写在for里面的。
class
Solution {
public
:
int
minCut(
string
s)
{
if
(s.size() ==
0
)
return
0
;
bool
mat[s.size()][s.size()];
memset(mat,
0
,
sizeof
(mat));
//
很久才发现没有初始化是错误的
for
(
int
i = s.size()-
1
; i >=
0
; --
i)
for
(
int
j = i; j < s.size(); ++
j)
{
if
((s[i] == s[j] && j - i <
2
) || (s[i] == s[j] && mat[i+
1
][j-
1
]))
mat[i][j]
=
true
;
}
int
cnt[s.size()+
1
];
//
最后一个为0，用于j+1溢出的操作
memset(cnt,
0
,
sizeof
(cnt));
for
(
int
i = s.size() -
1
; i >=
0
; --
i)
{
cnt[i]
= s.size() -
i;
for
(
int
j = i; j < s.size(); ++j)
//
j一定是从i开始，因为可能存在i是一个孤立的加上i+1到之后的最小值
{
if
(mat[i][j])
cnt[i]
= min(cnt[i], cnt[j +
1
] +
1
);
}
}
return
cnt[
0
] -
1
;
}
};
