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,转载请注明出处
如果本篇文章对您有帮助欢迎打赏哦！
微信打赏 支付宝打赏
关注公众号(烦嚣的人)
微信公众号