# JAVA DP recursive 5ms solution

• ``````public class Solution {
int[] cut;
public int minCut(String s) {
int len=s.length();
char[] tmp=s.toCharArray();
cut=new int[s.length()];
Arrays.fill(cut,Integer.MAX_VALUE);
for(int i=0;i<len;i++)
{
re(tmp,i,i);
re(tmp,i-1,i);
}
return cut[len-1];
}
public void re(char[] s,int start,int end)
{
if(start<0||end>=s.length)return;
if(s[start]==s[end])
{
re(s,start-1,end+1);
int tmp=start==0?0:cut[start-1]+1;
cut[end]=Math.min(tmp,cut[end]);
}
}
}``````

• @tjcd Could you explain it a little?

• @mishrasonu1993 if you write a top-down algorithm, you can see the relationship between two iterations is

``````dp[i][j] = (c[i]==c[j]&&dp[i+1][j-1])
``````

we only use the previous result which is inside the current string. we can do it by storing all data in 2-d array but we can also do it in a bottom-up way that is "from inside to outside". The benefit is that we can save that 2-d space and make algorithm faster. But I think top-down algorithm is ok when you are doing an interview I guess :).

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