题目

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

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

代码

public class DayCode {
    public static void main(String[] args) {
        String s = "aab";
        int ans = new DayCode().minCut(s);
        System.out.println("ans is " + ans);
    }
    /**
     * https://leetcode-cn.com/problems/palindrome-partitioning-ii/
     * @param s
     * @return
     */
    public int minCut(String s) {
        if (s == null || s.length() == 1) {
            return 0;
        }
        int len = s.length();
        int[] dp = new int[len];
        Arrays.fill(dp, len - 1);
        for (int i = 0; i < len; i++) {
            minCutHelper(s, i, i, dp);
            minCutHelper(s, i, i + 1, dp);
        }
        return dp[len - 1];
    }
    /**
     * @desc 如果以当前字符为中心的最大回文串左侧为i，右侧为j，
     那s[i]~s[j]长度是不需要切割的，只需要在s[i-1]处切一刀即可，即dp[i-1]+1。
     所以更新dp[j] = min(dp[j] , dp[i-1]+1)，不断往外扩散更新dp值取dp[-1]即可。
     * @param s
     * @param i
     * @param j
     * @param dp
     */
    public void minCutHelper(String s, int i, int j, int[] dp) {
        int len = s.length();
        while (i >= 0 && j < len && s.charAt(i) == s.charAt(j)) {
            dp[j] = Math.min(dp[j], (i == 0 ? - 1 : dp[i -1]) + 1);
            i--;
            j++;
        }
    }
}

总结

* 今天这个题目是昨天题目的延续，周一早上hard，开启活力满满的一天！

* 暴力法以外，优化的解法是思路的转变，采用动态规划的方法。

* 坚持每日一题，加油！