题目

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

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

示例1

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

题解

1. 动态规划。dp[i]代表前i个字符的最小分割次数，dp[i]最多可以分割i-1次
2. 若区间[j, i]是回文串，且dp[j]已知，则只需要再多分割一次将区间[j, i]分割出来
3. 故：dp[i] = Math.min(dp[i], dp[j]+1)

参考代码

class Solution {
    public int minCut(String s) {
        int len = s.length();
        int[] dp = new int[len+1];
        dp[0] = -1;
        for(int i = 1; i <= len; i++) {
            dp[i] = i - 1; // 最大分割次数
            for(int j = i; j >= 1; j--) {
                if(isVaild(s, j-1, i-1)) {
                    dp[i] = Math.min(dp[i], dp[j-1]+1);
                }
            }
        }
        return dp[len];
    }

    private boolean isVaild(String s, int i, int j) {
        while(i < j) {
            if(s.charAt(i) != s.charAt(j)) return false;
            i++;
            j--;
        }
        return true;
    }
}