Leetcode--Java--132. 分割回文串 II

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

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

示例 1：

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

输入：s = "a"
输出：0
示例 3：

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

动态规划 + 题意转化
最少划分次数，可以转化为求最少分为多少个部分，部分数减1就是所求。

1. 动态表示和动态计算，以最后一个为分析，例如f(i)可以表示最后一个可以来自的段为1~i,
   2 ~ i, i ~ i等。
2. 比如对于任意k, k ~ i，要使得划分次数最少，只要让1 ~ k - 1最少即可，因为k~i这段已确定。
   
3. 为了方便快速判断某段是否是回文串，先用dp做预处理，做法与这里完全一致。
   
4. 为了方便动态规划，让下标从1开始，让字符串先补充个空字符在前面。
5. 求最小的，一定要先赋个无穷大的初值。

class Solution {
    public int minCut(String s) {
       int n = s.length();
       s = ' ' + s;
       int f[] = new int[n + 1]; //f[i]表示划分为子串1~i，2~i...i ~ i中最少分割次数
       //先初始化为最大值
       Arrays.fill(f, Integer.MAX_VALUE);
       boolean g[][] = new boolean[n + 1][n + 1];
       //dp预处理，快速判断某段内是否存在回文串  
       for (int j = 1; j <= n; j ++ ) {
           for (int i = 1; i <= n; i ++ ) {
               //单个字符
               if (i == j) {
               g[i][j] = true;
               //相等字符的情况下
               }else if (s.charAt(i) == s.charAt(j)){
                   //相邻，或者中间有回文段
                   g[i][j] = (i + 1 > j - 1 || g[i + 1][j - 1]);
               }
           }
       }
       //0个字符，需要0次划分
       f[0] = 0;
       for (int i = 1; i <= n; i ++ ) {
           for (int j = 1; j <= i; j ++ ){
               //注意这里是g[j][i],表示j~i这个划分段
               if (g[j][i]) {
                   //动态转化为f[j - 1] + 1，因为j到i最小，使得到1到j - 1的划分段最少即可
                   f[i] = Math.min(f[i], f[j - 1] + 1);
               }
           }
       }
       //求的是划分段，次数要减1
       return f[n] - 1;
    }
}