dfs large沒過，看了網上的dp
1
class
Solution {
2
public
:
3
int
minCut(
string
s) {
4
int
n =
s.size();
5
vector<
int
> C(n+
1
);
6
vector<vector<
bool
> > P(n, vector<
bool
>
(n));
7
for
(
int
i =
0
; i < n; ++i) P[i][i] =
true
;
8
for
(
int
i =
0
; i <= n; ++
i) {
9
C[i] = n -
i;
10
}
11
for
(
int
i = n-
1
; i >=
0
; --
i) {
12
for
(
int
j = i; j < n; ++
j) {
13
if
(s[i] == s[j] && (j-i <
2
|| P[i+
1
][j-
1
])) {
14
P[i][j] =
true
;
15
C[i] = min(C[i],
1
+C[j+
1
]);
16
}
17
}
18
}
19
return
C[
0
]-
1
;
20
}
21
};
?C#
1
public
class
Solution {
2
public
int
MinCut(
string
s) {
3
int
n =
s.Length;
4
int
[] C =
new
int
[n+
1
];
5
bool
[,] P =
new
bool
[n, n];
6
for
(
int
i =
0
; i < n; i++) P[i, i] =
true
;
7
for
(
int
i =
0
; i <= n; i++) C[i] = n -
i;
8
for
(
int
i = n-
1
; i >=
0
; i--
) {
9
for
(
int
j = i; j < n; j++
) {
10
if
(s[i] == s[j] && (j-i <
2
|| P[i+
1
, j-
1
])) {
11
P[i, j] =
true
;
12
C[i] = Math.Min(C[i],
1
+ C[j+
1
]);
13
}
14
}
15
}
16
return
C[
0
] -
1
;
17
}
18
}
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
