public class Solution {
public int minCut(String s) {
if(s==null)
return 0;
int i,j,n=s.length();
int cuts[]=new int[n]; //cuts[i] will store the minimum no. of cuts required for substring [0...i];
boolean dp[][]=new boolean[n][n]; // dp[i][j]=true if substring [i...j] can be partitioned into list of palindromes.
for(i=0;i<n;i++)
{
/*since every single character is a palindrome, maximum no. of cuts for substring [0...i] will be i
hence initiating cuts[i] with maximum possible value. */
cuts[i]=i;
for(j=0;j<=i;j++)
{
if(j == i)
dp[j][i] = true;
else
{
if(s.charAt(i)!= s.charAt(j))
continue;
if(j==i1)
dp[j][i]=true;
else
dp[j][i]=dp[j+1][i1] ;
}
if(dp[j][i])
{
if(j==0)
cuts[i]=0;
else
cuts[i]=Math.min(cuts[j1]+1,cuts[i]);
/*since dp[j][i] is a palindrome, cuts[j]+1 equals no. of cuts required in [0...i] if we include the current word [j..i]; New cuts[i] will be equal to min of previous cuts[i] and the newly calculated cuts[i] i.e. cuts[j]+1 */
}
}
}
return cuts[n1];
}
}
My accepted O(n^2) DP solution in Java


This is a similar way using python.
class Solution(object): def minCut(self, s): """ :type s: str :rtype: int """ # cuts is used to store the number of cuts for s[:i+1]. The inital value means to cut every place cuts = [i for i in xrange(len(s))] # dp[j][i] is used to store if s[j:i+1] is palindrome. We initialize everything to False except those on diagonal dp = [[False if i!=j else True for i in xrange(len(s))] for j in xrange(len(s))] for i in xrange(len(s)): for j in xrange(i+1): if s[i]==s[j]: # if there are no more letters between j and i, then we assign True, else move "inside" one step dp[j][i] = True if ij<=1 else dp[j+1][i1] if dp[j][i]: # because s[j:i+1] is palindrome, we can update cuts[i] cuts[i] = 0 if j==0 else min(cuts[j1]+1, cuts[i]) return cuts[1]