分割回文串 II[动规典中典]

前言

动态规划就像贪心一样，高质量考察逻辑分析和问题分解的能力。但动态规划却比贪心更明确一点，将大问题拆解成规模更小性质相同的小问题进行递推中，找到状态 & 状态转移，则能用空间换时间，否则迎接而来的就算N方或指数级复杂度。

一、最少分割回文串次数

二、DFS + 剪枝 || 动规

1、DFS + 剪枝 = timeout

// 分割回文串II
public class MinCut {
    /*
    target：分割回文串的最少次数。
    1-分割成回文列表的次数？该列表的size - 1；
    2-最少次数？用一个变量记录最小的即可。
    idea：先标准字符串的各项字串是否为回文，再dfs去组合，配合已得的min去剪枝。
    result：timeout
    idea2：动态规划，f[i]表示s[0:i]字串最小分割次数。
     */
    public int minCut(String s) {
        // abba cdeedcab
        int n = s.length();
        // 标注字符串的子串是否为回文。
        boolean[][] isPa = isPalindrome(s);
        // dfs 获取最小分割次数。
        dfs(s, 0, 0, isPa);
        // 返回最小分割次数。
        return min;
    }

    private void dfs(String s, int cur, int size, boolean[][] isPa) {
        if (cur == s.length()) {
            min = size - 1;

            return;
        }
        if (size - 1 >= min) return;

        for (int i = 0; i + cur < s.length(); i++) {
            if (isPa[cur][i + cur]) dfs(s, cur + i + 1, size + 1, isPa);
        }
    }

    int min = 1 << 30;

    private boolean[][] isPalindrome(String s) {
        int n = s.length();
        boolean[][] isPa = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            isPa[i][i] = true;

            for (int j = i - 1; j >= 0; j--) {
                if (s.charAt(i) == s.charAt(j) && (j + 1 == i || isPa[j + 1][i - 1]))
                    isPa[j][i] = true;
            }
        }
        return isPa;
    }
}
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
41
42
43
44
45
46
47
48
49
50
51

2、动规

// idea2：动态规划，f[i]表示s[0:i]字串最小分割次数。
class MinCut2 {
    /*
    target：分割回文串的最少次数。
    1-分割成回文列表的次数？该列表的size - 1；
    2-最少次数？用一个变量记录最小的即可。
    idea：先标准字符串的各项字串是否为回文，再dfs去组合，配合已得的min去剪枝。
    result：timeout
    idea2：动态规划，f[i]表示s[0:i]字串最小分割次数。
    // review：
    // 1-动态规划要多练，找规律太看题感了，没有大量的沉淀，根本找不到角度。
    // 2-看题解虽一下秒懂，但是里面细节其实很多，需要大量的沉淀，才能完美的把控各种细节，做到见招拆招。
    // 3-除了细节多外，就算把细节都处理了，题解区竟然还有巧妙的做法，一种殊途同归鸡皮疙瘩的处理方式。
    // 比如Arrays.fill(isPa[i],true) 配合 isPa[j][i] = s.charAt(i) == s.charAt(j) && isPa[j+1][i-1]。
    // 根本不需要if，让CPU一直算即可。

    // 再比如for (int j = 1; j <= i; j++) { 后面用f[j - 1]，而题解是for (int j = 0; j < i; j++) {直接用f[j]。
    // 虽然一样，但这种方式不是直观方式，是有小设计在里面的 = 直观+小思考进行转换。

    // 4-综上，大量练题好处(多看评论区，进行一题多解。)，即量(这个量是独立思考+学习他人的量，而不是单纯的磨时间。)的重要性，a-有题感能快速找到分析角度和规律；b-大量细节可做到灵活的见招拆招，而不是死板坐牢浪费时间。
    // 除此之外，不得不说动态规划 是 解决指数级dfs的锦囊妙计（一般情况下，两种容易关联。）。
     */
    public int minCut(String s) {
        // abba cdeedcab
        // abba b || a b bab
        int n = s.length();
        // 标注字符串的子串是否为回文。
        boolean[][] isPa = isPalindrome(s);
        // 动态规划，本质结合贪心，把最大的回文分割出来，剩下的字符串，会有前面的状态记录。
        int[] f = new int[n];
        for (int i = 0; i < n; i++) {
            if (isPa[0][i]) continue;// 默认f[i] = 0;

            f[i] = 1 << 30;// 先设位最大，然后找最小分割次数。
            for (int j = 1; j <= i; j++) {
                // 取从任意j转移到i 最小的分割次数。
                if (isPa[j][i]) f[i] = Math.min(f[i],f[j - 1] + 1);

            }
        }
        return f[n - 1];
    }

    private boolean[][] isPalindrome(String s) {
        int n = s.length();
        boolean[][] isPa = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            isPa[i][i] = true;

            for (int j = i - 1; j >= 0; j--) {
                if (s.charAt(i) == s.charAt(j) && (j + 1 == i || isPa[j + 1][i - 1]))
                    isPa[j][i] = true;
            }
        }
        return isPa;
    }
}
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

总结

1）动态规划要多练，找规律太看题感了，没有大量的沉淀，根本找不到角度。

2）看题解虽一下秒懂，但是里面细节其实很多，需要大量的沉淀，才能完美的把控各种细节，做到见招拆招。

3）除了细节多外，就算把细节都处理了，题解区竟然还有巧妙的做法，一种殊途同归鸡皮疙瘩的处理方式。

4）两种二维动规，一种是状态也是二维的，必须N方来递推；一种状态一维，但递推时需要前面的所有状态。

参考文献

[1] LeetCode 分割回文串 II