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,i1,i);
}
return cut[len1];
}
public void re(char[] s,int start,int end)
{
if(start<0end>=s.length)return;
if(s[start]==s[end])
{
re(s,start1,end+1);
int tmp=start==0?0:cut[start1]+1;
cut[end]=Math.min(tmp,cut[end]);
}
}
}
JAVA DP recursive 5ms solution



@mishrasonu1993 if you write a topdown algorithm, you can see the relationship between two iterations is
dp[i][j] = (c[i]==c[j]&&dp[i+1][j1])
we only use the previous result which is inside the current string. we can do it by storing all data in 2d array but we can also do it in a bottomup way that is "from inside to outside". The benefit is that we can save that 2d space and make algorithm faster. But I think topdown algorithm is ok when you are doing an interview I guess :).