题目描述：

给定字符串 s, 需要将它分割成一些子串, 使得每个子串都是回文串.

最少需要分割几次?

样例

样例 1:

输入:
"a"
输出:
0
解释: 
"a" 本身就是回文串, 无需分割

样例 2:

输入:
"aab"
输出:
1
解释:
将 "aab" 分割一次, 得到 "aa" 和 "b", 它们都是回文串.

思路：

这里我们最主要的就是如何判断出指定区间的字符串为回文串，我们可以从前往后，以每一个字符为基石，让其往两边伸展，然后考虑奇偶性，因为一个回文串的长度要么是奇数，要么是偶数，就这两种情况，所以我们就可以定住每一个中间字符，向外扩展，判断这个字符串中哪些区间是回文串，哪些不是。并用一个二维的布尔类型数组记录每一个区间是否为回文串，接下来考虑最后一步就很容易了，我们知道最后一步一定是从第j个位置分割，将第j + 1个字符到最后一个字符划分为一个回文串，当我们考虑前i个字符的串是否为回文串时，我们就需要从第一个字符遍历到第i个字符，从中找到最少分割次数并更新。这样一来我们就把考虑前i个字符的串最少分割几次，转变为前j个字符的串最少分割几次。

转移方程：f[i] = min{f[i], f[j] + 1}

 

AC代码：

 1 public class Solution {
 2     /**
 3      * @param s: A string
 4      * @return: An integer
 5      */
 6     public int minCut(String s) {
 7         // write your code here
 8         if (s == null || s.length() == 0) {
 9             return 0;
10         }
11 
12         char[] c = s.toCharArray();
13         int n = c.length;
14 
15         boolean[][] isPalins = new boolean[n][n];
16 
17         // initialization
18         for (int i = 0; i < n; i++) {
19             for (int j = 0; j < n; j++) {
20                 isPalins[i][j] = false;
21             }
22         }
23 
24         // 定基准
25         for (int t = 0; t < n; t++) {
26             int i, j;
27             // 默认一个字符也是回文串
28             i = t;
29             j = t;
30 
31             // odd
32             while (i >= 0 && j < n && c[i] == c[j]) {
33                 isPalins[i][j] = true;
34                 i--;
35                 j++;
36             }
37 
38             i = t;
39             j = t + 1;
40             // even
41             while (i >= 0 && j < n && c[i] == c[j]) {
42                 isPalins[i][j] = true;
43                 i--;
44                 j++;
45             }
46         }
47 
48         // 定义状态：dp[i] 代表前i个字符中回文串的个数
49         int[] dp = new int[n + 1];
50 
51         // 初始化
52         dp[0] = 0;
53 
54         for (int i = 1; i <= n; i++) {
55             // 因为这里是取最小值，所以一开始要设为无穷大
56             // 任意一个字符串（空串除外）都能化成若干个回文串（因为单个字符就是一个回文串），所以一定可以分割出来，即这里设置为无穷大也就没啥问题
57             dp[i] = Integer.MAX_VALUE;
58             // 从第一个字符一直遍历到第i个字符。挨个判断，取最小值
59             for (int j = 0; j < i; j++) {
60                 if (isPalins[j][i - 1]) {
61                     // is Palin
62                     dp[i] = Math.min(dp[i], dp[j] + 1);
63                 }
64             }
65         }
66 
67         // 别忘了本题是让我们求最小需要分割几次，所有最后要-1
68         return dp[n] - 1;
69     }
70 }