Q132 分割回文串2(palindrome-partitioning-ii)

解析思路

leetcode 中等难度,题目描述点击这里

经过分割回文数后,本题应该就比较简单了。

题目要求返回最少的分割次数,通常这类最优问题都可以用 dp 来解决。注意这里无法使用上题的 dfs 暴力穷举所有结果后找到最优,会超时(因为字符长度最大为 2000,上题为 16)。

如果要用 dp 那么就需要构建 dp 表达式:

定义 minC[k]表示从 0 到 k 的最小分割次数,递推关系如下:

  1. minC[k] = 0 ,k==0 || dp[0][k],当 k=0 或者 0-k 是一个回文串
  2. minC[k] = min(min[r-1]+1).其他情况需要在 0 到 k 之间找到一个 r 使 r 到 k 为一个回文数,那么分割次数就是 minC[r-1]+1(0 到 r-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
public class Q132 {

public int minCut(String s) {
//先用dp找到所有符合条件的回文
boolean[][] dp = new boolean[s.length()][s.length()];
for (int j = 0; j < dp.length; j++) {
for (int i = 0; i <= j; i++) {
if (i == j) {
dp[i][j] = true;
} else {
boolean b = s.charAt(i) == s.charAt(j);
if (i + 1 == j) {
dp[i][j] = b;
} else {
dp[i][j] = dp[i + 1][j - 1] && b;
}
}
}
}
//再次dp找到最小分割次数.定义minArr[i]为从0到i的最小分割次数
int[] minArr = new int[s.length()];
for (int i = 1; i < s.length(); i++) {
//定义l,当l->i构成回文串时,此时分割次数为=minArr[l-1]+1.找到最小的l
int temp = i;
for (int l = 0; l <= i; l++) {
if (dp[l][i]) {
temp = Math.min(temp, l == 0 ? 0 : minArr[l - 1] + 1);
}
}
minArr[i] = temp;
}
return minArr[s.length() - 1];
}


public static void main(String[] args) {
System.out.println(new Q132().minCut("aab"));
}
}
本文原创发布于:https://blog.fleyx.com,转载请注明出处

如果本篇文章对您有帮助欢迎打赏哦!
微信打赏 支付宝打赏
关注公众号(烦嚣的人)
微信公众号