Palindrome Partitioning II leetcode

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

求最优解法的一般都用dp

state: dp[i] 表示前i个字符最少需要几次cut才能符合要求

function：dp[i] = min(dp[j] +1) //前提substring(j,i)也是回文串

initial  dp[i] = i -1(dp[0] = -1)

return dp[s.length]

那么问题又来了 在判断substring是不是回文串的时候也是个DP问题 如果每次都判定的话复杂度在O（n^3） 如果使用DP可以下降到O(n^2)
时间O(n^2) 空间O(n^2)

state: p[i][j] = true 表示字符串[i,j]从第i个位置（包含）到第j个位置（包含） 是否是回文。

function： p[i][j] = (str[i] == str[j] && p[i+1][j-1]) 因为要判定i + 1 和j - 1 所以 i要从高往低递减 j 递增

initail: 当i+1 = j时候 p[i][j] = str[i] == str[j] , i == j 时候 p[i][j]为true

return p[i, j]

public class Solution {
    public int minCut(String s) {
        if (s.length() == 0 || s == null) {
            return 0;
        }
        boolean[][] map = getmap(s);
        int[] dp = new int[s.length() + 1];
        for (int i = 0; i <= s.length(); i++) {//初始化0为-1， 1为0,包括0这一项是因为可能从0到i整个字串都为回文串 这样返回dp[0]+1 =0
            dp[i] = i - 1;
        }
        for (int i = 2; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (map[j][i-1]) {//这里对应着substring j+1 到i 是否为回文串
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[s.length()];
    }
    private boolean[][] getmap(String s) {
        boolean[][] map = new boolean[s.length()][s.length()];
        for (int i = s.length() - 1; i >=0 ; i--) {//因为每次取i+1 所以i要递减
            for (int j = i; j < s.length(); j++) {
                if (i == j){
                    map[i][j] = true;
                }
                else if (i + 1 == j) {
                    map[i][j] = s.charAt(i) == s.charAt(j);
                }
                else {
                    map[i][j] = s.charAt(i) == s.charAt(j) && map[i+1][j-1];
                }
            }
        }
        return map;
    }
}