Palindrome Partitioning II

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

class Solution {
public:
    int minCut(string s) {
        int len = s.size();
        bool P[len][len];
        int dp[len + 1];
        for (int i = 0; i <= len; ++i) {
            dp[i] = len - i - 1;
        }
        for (int i = 0; i < len; ++i) {
            for (int j = 0; j < len; ++j) {
                P[i][j] = false;
            }
        }
        for (int i = len - 1; i >= 0; --i) {
            for (int j = i; j < len; ++j) {
                if (s[i] == s[j] && (j - i <= 1 || P[i + 1][j - 1])) {
                    P[i][j] = true;
                    dp[i] = min(dp[i], dp[j + 1] + 1);
                }
            }
        }
        return dp[0];
    }
};