71 lines
2.6 KiB
Markdown
71 lines
2.6 KiB
Markdown
---
|
||
id: "202203091"
|
||
date: "2022/03/09 22:15"
|
||
title: "Q132 分割回文串2(palindrome-partitioning-ii)"
|
||
tags: ["java", "leetcode", "dp"]
|
||
index_img: https://qiniupic.fleyx.com/blog/202203091652083.png?imageView2/2/w/200
|
||
banner_img: https://qiniupic.fleyx.com/blog/202203091652083.png
|
||
categories:
|
||
- "算法"
|
||
- "leetcode刷题"
|
||
---
|
||
|
||
### 解析思路
|
||
|
||
leetcode 中等难度，题目描述[点击这里](https://leetcode-cn.com/problems/palindrome-partitioning-ii/)。
|
||
|
||
经过[分割回文数](https://blog.fleyx.com/blog/detail/20220309)后，本题应该就比较简单了。
|
||
|
||
题目要求返回最少的分割次数，通常这类最优问题都可以用 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 需要的最小分割次数再加上一次分割),在所有的情况下取最小的那个即可
|
||
|
||
### 代码如下：
|
||
|
||
```java
|
||
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"));
|
||
}
|
||
}
|
||
```
|