题目描述
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的最少分割次数。
题解
使用动态规划的方法，可以利用上次的动态规划判断回文字符串的方法做优化。
dp[i]：前缀子串 s[0:i] （包括索引 i 处的字符）符合要求的最少分割次数
状态转移方程： dp[i] = min(dp[j] + 1 if s[j + 1: i] 是回文 for j in range(i))
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
| int minCut(string s) {
int slen = s.length();
bool **isPali = new bool*[slen];
for (int i = 0; i < slen; i++)
isPali[i] = new bool[slen];
for (int i = 0; i < slen; i++)
isPali[i][i] = 1;
for (int i = 1; i < slen; i++)
isPali[i][i - 1] = 1;
for (int i = 1; i < slen; i++)
{
for (int j = 0; j < slen-i; j++)
{
isPali[j][i + j] = isPali[j + 1][i + j - 1] && (s[j] == s[i + j]);
}
}
int* dp = new int[slen];
for (int i = 0; i < slen; i++)
dp[i] = i;
for (int i = 1; i < slen; i++)
{
if (isPali[0][i])
{
dp[i] = 0;
continue;
}
for (int j = 0; j < i; j++)
{
if (isPali[j + 1][i])
{
dp[i] = min(dp[j] + 1, dp[i]);
}
}
}
return dp[slen - 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
| bool **dp;
int slen = 0;
void dfsHelper(string& s,int ps,int& tmp,int& res)
{
if (tmp > res)return;
if (ps >= slen)
{
res = tmp < res ? tmp : res;
return;
}
for (int i = ps; i < slen; i++)
{
if (dp[ps][i])
{
tmp++;
dfsHelper(s, i + 1, tmp, res);
tmp--;
}
}
}
int minCut(string s) {
slen = s.length();
dp = new bool*[slen];
for (int i = 0; i < slen; i++)
dp[i] = new bool[slen];
for (int i = 0; i < slen; i++)
dp[i][i] = 1;
for (int i = 1; i < slen; i++)
dp[i][i - 1] = 1;
for (int i = 1; i < slen; i++)
{
for (int j = 0; j < slen-i; j++)
{
dp[j][i + j] = dp[j + 1][i + j - 1] && (s[j] == s[i + j]);
}
}
int res = slen, tmp = 0;
dfsHelper(s,0, tmp, res);
return res-1;
}
|
还是很菜啊……所以更不能一直躺着啊……