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.
这道题很惭愧，想直接在上一道题的代码上改，结果还是重写了。
之前为了方便算回文，插入“#”。但是程序会报内存不足，所以不能用这种扩展方式，只能拿string.size来建dp数组
后面根据数组，用dp继续做cut。cut的时候 cut j = min（cut j ， cut i +1 （if dp[i+1][j] == 1））.要注意该推导式不需要dp[0][i] == 1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58 |
class
Solution {public: int
minCut(string s) { vector<vector <int> >dp; int
len = s.size(); if(len == 1)return
0; for(int
i = 0 ; i < len ;i++) { vector<int> tp(len,0); dp.push_back(tp); } for(int
i = 0 ; i < len ; i++) dp[i][i] = 1; for(int
i = 0 ; i < len ;i++) { int
j = 1; while(i-j>=0 && i+j<len && s[i-j] == s[i+j]) { dp[i-j][i+j] = 1; j++; } int
x = i , y =i+1; while(x>=0 && y<len) { if(s[x]==s[y]) { dp[x][y]=1; x--; y++; } else break; } } int
num = 0; if(dp[0][len-1]==1)return
0; vector<int> cut(len ,1); for(int
i = 0 ; i < len ;i++) if(dp[0][i]==1)cut[i] = 1; else cut[i] = i+1; for(int
i = 1;i<len;i++) { for(int
j = 0 ;j <i ;j++) { if(j+1<len && dp[j+1][i]==1) { cut[i] = min(cut[j]+1,cut[i]); } } } return
cut[len-1]-1; }}; |
Palindrome Partitioning II,布布扣,bubuko.com
原文：http://www.cnblogs.com/pengyu2003/p/3669533.html