# My java dp solution

1. flags[i][j] expresses substring from i to j is palindrome or not.
2. dp[i] expresses min cut of substring from 0 to i .
3. dp[i] = min(dp[i-j1]+1,dp[i-j2] +1,...dp[i-jn] +1) j1,j2,...jn < j && s[i] == s[i-ji+1] && flags[i-ji+2][i-1]

``````public int minCut(String s) {
if(s == null || s.length() == 0 || s.length() == 1) return 0;
int[] dp = new int[s.length()];
boolean[][] flags = new boolean[s.length()][s.length()];
flags[0][0] = flags[1][1] = true;
flags[0][1] = s.charAt(0) == s.charAt(1) ? true : false;
dp[1] = flags[0][1] ? 0 : 1;
for(int i = 2; i < s.length(); i++){
dp[i] = dp[i-1] + 1;
flags[i][i] = true;
for(int j = 0; j < i; j++){
if(s.charAt(i) == s.charAt(j)){
if(j == i-1){
dp[i] = Math.min(dp[i],dp[i-2] + 1);
flags[i-1][i] = true;
}
else if(flags[j+1][i-1]){
dp[i] = Math.min(dp[i],j == 0 ? 0 : (dp[j-1] + 1));
flags[j][i] = true;
}
}
}
}
return dp[s.length()-1];
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.