lintcode108- Palindrome Partitioning II- medium

Given a string s, cut s into some substrings such that every substring is a palindrome.

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

Example

Given s = "aab",

Return 1 since the palindrome partitioning ["aa", "b"] could be produced using 1 cut.

动态规划。这题不要你把所有可能性打印出来了，所以没必要用时间复杂度太高的DFS。这题求最优解，用动态规划。想到求“前n个字符最少可以分成几个”可以拆解为借助“前n-1个字符最少可以分成几个”、“前n-2个字符最少可以分成几个”等等等来实现的问题。如果某个点j开始到n是回文串，那么“前 n 个字符可以分成几个”问题的一个可能解就是“前 j 个字符最少可以分成几个”+1，把j一个个试过来，最小的那个就是答案。

f[n]: 前n个字符最少可以分成几个

f[n] = min {f[j] + 1} ( j需要满足从j+1~n是回文串，0<j<n)

public class Solution {
    /**
     * @param s a string
     * @return an integer
     */
    
    private int minCut = Integer.MAX_VALUE;
    
    public int minCut(String s) {
        // write your code here
        if (s == null || s.length() == 0) {
            return -1;
        }
        
        boolean[][] isPalindrome = isPalindrome(s);
        // 前n个字母里最少可以分出多少个回文串
        int[] f = new int[s.length() + 1];
        f[0] = 0;
        
        for (int i = 1; i < s.length() + 1; i++) {
            f[i] = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                if (!isPalindrome[j][i - 1]) {
                    continue;
                }
                f[i] = Math.min(f[i], f[j] + 1);
            }
        }
        return f[s.length()] - 1;
    }
    
    private boolean[][] isPalindrome(String s) {
        boolean[][] isPalindrome = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            isPalindrome[i][i] = true;
        } 
        
        for (int i = 1; i < s.length(); i++) {
            isPalindrome[i - 1][i] = s.charAt(i - 1) == s.charAt(i);
        }
        
        for (int i = s.length() - 3; i >= 0; i--) {
            for (int j = i + 2; j < s.length(); j++) {
                isPalindrome[i][j] = isPalindrome[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
            }
        }
        return isPalindrome;
    }
    
};