Leetcode 132 Palindrome Partitioning II

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.

Solution 1: Use DP. dp[i][j] store if s[i..j] is palindrome or not. res[j] is the min cut of s[0..j]. In the loop, keep update dp[i][j] matrix and res[j] array. The complexity is O(N^2).

 public class Solution {  
   public int minCut(String s) {  
     int n=s.length();  
     char[] c=s.toCharArray();  
     boolean[][] dp=new boolean[n][n];  
     int[] res=new int[n];  
     for (int j=0; j<n; j++) {  
       res[j]=Integer.MAX_VALUE;  
       for (int i=j; i>=0; i--) {  
         dp[i][j]=i==j || (c[i]==c[j] && (i+1>=j-1 || dp[i+1][j-1]));  
         if (dp[i][j]) {  
           int cut=(i==0)?0:res[i-1]+1;  
           res[j]=Math.min(res[j],cut);  
         }  
       }  
     }  
     return res[n-1];  
   }  
 }