# My accepted O(n^2) DP solution in Java

• ``````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==i-1)

dp[j][i]=true;
else
dp[j][i]=dp[j+1][i-1] ;
}

if(dp[j][i])
{
if(j==0)
cuts[i]=0;
else
cuts[i]=Math.min(cuts[j-1]+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[n-1];

}
}``````

• It's so far the easiest and clearest one to understand

• 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 i-j<=1 else dp[j+1][i-1]
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[j-1]+1, cuts[i])
return cuts[-1]``````

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