Palindrome Partitioning II (LeetCode Dynamic Programming)

Question: 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.

Idea: Duo-Dynamic programming. Let P[i][j] stand for whether the substring between i and j is a palindrome. Then we just need to compare the two ends of i and j to derive the recursive function. P[i][j]==true if s[i]==s[j]&&P[i+1][j-1]==true or the substring has less than 2 characters (j-i<2). Then use another array variable D[] to cache the total number of partitions. In the worst case, each character of the input string will be split as a palindrome. Then if we found s[i->j] is a palindrome through P[i][j], we can fill the data into D. This can be done at the same time as calculating P[i][j] or in another individual loop.

Time: O(n^2) Space: O(n^2)

Code:

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