553，动态规划解分割回文串 II

Original 博哥数据结构和算法 2022-05-01

收录于合集 #算法图文分析 161个

When a man's stories are remembered, then he is immortal.

一个人的故事被记住了，他就千古不朽。

问题描述

来源：LeetCode第132题

难度：困难

给你一个字符串s，请你将s分割成一些子串，使每个子串都是回文。

返回符合要求的最少分割次数。

示例 1：

输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

示例 2：

输入：s = "a"
输出：0

示例 3：

输入：s = "ab"
输出：1

提示：

1 <= s.length <= 2000
s 仅由小写英文字母组成

动态规划解决

前面刚讲过《551，回溯算法解分割回文串》，第551要求返回所有可能分隔的结果，而这题要求返回最小的分隔次数。如果数据量不大的话我们是可以使用第551题的答案的，找出第551题所有可能分隔的方案中最小的分隔次数就是我们这题的答案。

但这题提示中明显数量比较大，所以使用回溯算法是行不通的，我们可以改成动态规划来解决。

定义dp[i]表示字符串前i个字符构成的子串能分隔的最少分隔次数，如果要求s的最少分隔次数，只需要返回dp[length-1]即可（length是字符串s的长度）。

1，如果子串从[0…i]是回文是，就不需要分隔，即

dp[i]=0;

2，如果子串从[0…i]不是回文的，我们就需要从子串[0…i]后面截取一个回文的子串[j…i]，所以子串[0…i]可以分隔为[0…j-1]和[j…i]，而[0…j-1]的最小分隔次数就是dp[j-1]，[j…i]是一个回文串，不需要分隔，所以dp[i]=dp[j-1]+1，因为要求的是截取的最小次数，所以我们只需要保留最小的即可，即

dp[i]=min(dp[i],dp[j-1]+1);

如下图所示

因为这里求最小值，默认值我们给他每个都初始化最大的，来看下代码

 1public int minCut(String s) {
 2    int length = s.length();
 3    int[] dp = new int[length];
 4    //字符串s的回文子串最大也只能是字符串的长度length，
 5    //所以这里都默认初始化为最大值
 6    Arrays.fill(dp, length);
 7    for (int i = 0; i < length; ++i) {
 8        //如果字符串从0到i本身就是一个回文的，就不需要分隔，
 9        //直接返回0
10        if (palindrome(s, 0, i)) {
11            dp[i] = 0;
12        } else {
13            //否则就要分隔，找出最小的分隔方案
14            for (int j = 1; j <= i; ++j) {
15                if (palindrome(s, j, i)) {
16                    dp[i] = Math.min(dp[i], dp[j - 1] + 1);
17                }
18            }
19        }
20    }
21    return dp[length - 1];
22}
23
24//判断从left到right之间的子串是否是回文的（使用双指针判断）
25private boolean palindrome(String s, int left, int right) {
26    while (left < right) {
27        if (s.charAt(left++) != s.charAt(right--))
28            return false;
29    }
30    return true;
31}

动态规划代码优化

上面代码虽然也能给解决，但每次截取的时候都要判断一遍是否是回文的，明显效率不是很高，我们还可以先计算他的每个子串是否是回文的，在截取的时候直接用即可，回文串的判断前面刚介绍过，《540，动态规划和中心扩散法解回文子串》，这里就不在重复介绍。我们可以先把代码复制过来

 1    int length = s.length();
 2    //判断子串[i…j]是否是回文串
 3    boolean[][] dp = new boolean[length][length];
 4    for (int j = 0; j < length; j++) {
 5        for (int i = 0; i <= j; i++) {
 6            //如果i和j指向的字符不一样，那么dp[i][j]就
 7            //不能构成回文字符串
 8            if (s.charAt(i) != s.charAt(j))
 9                continue;
10            dp[i][j] = j - i <= 2 || dp[i + 1][j - 1];
11        }
12    }
13

再来看下最终代码

 1public int minCut(String s) {
 2    int length = s.length();
 3    int[] dp = new int[length];
 4
 5    //判断子串[i…j]是否是回文串
 6    boolean[][] palindrome = new boolean[length][length];
 7    for (int j = 0; j < length; j++) {
 8        for (int i = 0; i <= j; i++) {
 9            //如果i和j指向的字符不一样，那么dp[i][j]就
10            //不能构成回文字符串
11            if (s.charAt(i) != s.charAt(j))
12                continue;
13            palindrome[i][j] = j - i <= 2 || palindrome[i + 1][j - 1];
14        }
15    }
16
17    //字符串s的回文子串最大也只能是字符串的长度length，
18    //所以这里都默认初始化为最大值
19    Arrays.fill(dp, length);
20    for (int i = 0; i < length; ++i) {
21        //如果字符串从0到i本身就是一个回文的，就不需要分隔，
22        //直接返回0
23        if (palindrome[0][i]) {
24            dp[i] = 0;
25        } else {
26            //否则就要分隔，找出最小的分隔方案
27            for (int j = 1; j <= i; ++j) {
28                if (palindrome[j][i]) {
29                    dp[i] = Math.min(dp[i], dp[j - 1] + 1);
30                }
31            }
32        }
33    }
34    return dp[length - 1];
35}