offer2-94

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int minCut(String s) {
        int[] dp = new int[s.length() + 1];
        Boolean[][] symmetric = new Boolean[s.length()][s.length()];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = -1;
        dp[1] = 0;

        for (int i = 1; i < s.length(); i++) {
            for (int j = 0; j <= i; j++) {
                if (isSymmetric(symmetric, s, j, i)) {
                    dp[i + 1] = Math.min(dp[j] + 1, dp[i + 1]);
                }
            }
        }

        return dp[s.length()];
    }


    private boolean isSymmetric(Boolean[][] symmetric, String s, int from, int to) {
        if (from > to) {
            return false;
        }

        if (symmetric[from][to] != null) {
            return symmetric[from][to];
        }

        if (from == to) {
            symmetric[from][to] = true;
            return symmetric[from][to];
        }

        if (from + 1 == to) {
            symmetric[from][to] = s.charAt(from) == s.charAt(to);
            return symmetric[from][to];
        }

        boolean result = (s.charAt(from) == s.charAt(to)) && isSymmetric(symmetric, s, from + 1, to - 1);
        symmetric[from][to] = result;
        return result;
    }
}
//leetcode submit region end(Prohibit modification and deletion)