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
}
