🔴 剑指 Offer II 094. 最少回文分割

LeetCode 提示

题目难度 困难

原题链接 🔗 leetcode

题解1

两部分：

一是如何判断substring回文串？用二维数组做记忆化搜索

二是怎么判断最小分割？用一维数组做动态规划

抄作业

class Solution {    public int minCut(String s) {        int n = s.length();        boolean[][] pa = new boolean[n][n];        for (int i=0; i<n; i++) {            Arrays.fill(pa[i], true);        }
        for (int i=n-1; i>=0; i--) {            for (int j=i+1; j<n; j++) {                pa[i][j] = s.charAt(i) == s.charAt(j) && pa[i+1][j-1];            }        }
        int[] dp = new int[n];        Arrays.fill(dp, Integer.MAX_VALUE);        dp[0] = 0;        for (int i=1; i<n; i++) {            if (pa[0][i]) {                dp[i] = 0;            } else {                for (int j=1; j<=i; j++) {                    if (pa[j][i]) {                        dp[i] = Math.min(dp[i], dp[j-1]+1);                    }                }            }        }
        return dp[n-1];    }}