Dynamic Programming - Palindrome Partitioning II

Usually the problems to find the optimal solutions, can be resolved by dynamic programming… so Assume that res[i] and res[j + 1] + 1… the smaller one is the solution we are looking for…. but the key is to loop from tail to head, and secondary loop is based on the first one.

Following this idea, only charAt[i] == charAt[j], and j and i are either next to each or only one in the middle… or charAt[i + 1] == charAt[j - 1] since j (secondary loop) is based on first one (i)… update the res[i] until 0 … return res[0] - 1


public class Solution {
    public int minCut(String s) {
        if(s == null || s.length() == 0){
            return Integer.MIN_VALUE;
        }
        if(s.length() == 1){
            return 0;
        }
        boolean[][] process = new boolean[s.length()][s.length()];
        int[] res = new int[s.length() + 1];
        for(int i = 0; i <= s.length(); i++){
            res[i] = s.length() - i;
        }
        for(int i = s.length() - 1; i >= 0; i--){
            for(int j = i; j < s.length(); j++){
                if(s.charAt(j) == s.charAt(i) && (j - i < 2 || process[i+1][j-1])){
                    process[i][j] = true;
                    res[i] = Math.min(res[j+1] + 1, res[i]);
                }
            }
        }
        return res[0] - 1;
    }
}