題目和上題一樣 leetcode Palindrome Partitioning ，這里需要求的是最小的分割數(shù)，也就是上一題的所有可能里面最少的一個分割。例如：
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(luò)是否可能為回文。判斷i到j(luò)是回文有兩種情況：
1.如果i到j(luò)的長度為1，也就是j-i=0那肯定就是回文了，如果長度為2并且s[i] == s[j]那也是回文。長度為其他的就用下一點判斷了
2.i到j(luò)是回文，那么i+1到j(luò)-1是回文，并且s[i] == s[j]。
所以可以用第1點初始化，然后利用第2點擴展所有。或者可以說為了能夠使用第2點dp求解，第1點是必須的。然后i從末尾開始，j從i開始，這樣每次需要第2點的時候第一點都已經(jīng)做完了。所以初始化可以一起寫在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));
//
很久才發(fā)現(xiàn)沒有初始化是錯誤的
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
;
}
};
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
