I used DP in 2 dimensional array to solve the palindrome problem and this cut problem. To avoid Arrays.fill(), I let both the value of pal[][] and cut[][] be of the true value+1. But it goes TLE in the "apjesgpsxoeiokmqmfgvjslcjukbqxpsobyhjpbgdfruqdkeiszrlmtwgfxyfostpqczidfljwfbbrflkgdvtytbgqalguewnhvvmcgxboycffopmtmhtfizxkmeftcucxpobxmelmjtuzigsxnncxpaibgpuijwhankxbplpyejxmrrjgeoevqozwdtgospohznkoyzocjlracchjqnggbfeebmuvbicbvmpuleywrpzwsihivnrwtxcukwplgtobhgxukwrdlszfaiqxwjvrgxnsveedxseeyeykarqnjrtlaliyudpacctzizcftjlunlgnfwcqqxcqikocqffsjyurzwysfjmswvhbrmshjuzsgpwyubtfbnwajuvrfhlccvfwhxfqthkcwhatktymgxostjlztwdxritygbrbibdgkezvzajizxasjnrcjwzdfvdnwwqeyumkamhzoqhnqjfzwzbixclcxqrtniznemxeahfozp" case, I used System.currentTimeMillis() and got it's 175ms to 230ms. Are there some more space to make improvement? Thanks.

```
public static int pal(int i,int j,String s,int[][] pal){
if(pal[i][j]!=0)
return pal[i][j];
if(j-i<=1){
pal[i][j]=2;
return 2;
}
if(s.charAt(i)==s.charAt(j-1)){
pal[i][j]=pal(i+1,j-1,s,pal);
return pal[i][j];
}
else{
pal[i][j]=1;
return 1;
}
}
public static int cut(int i,int j,String s,int[][] cut,int[][] pal){
if(cut[i][j]!=0){
return cut[i][j];
}
if(pal(i,j,s,pal)==2){
cut[i][j]=1;
return 1;
}
int min=j-i;
int tmp=min;
for(int mid=i+1;mid<j;mid++){
tmp=cut(i,mid,s,cut,pal)+cut(mid,j,s,cut,pal);
if(tmp<min)
min=tmp;
if(tmp==2)
break;
}
cut[i][j]=min;
return min;
}
public static int minCut(String s) {
int len=s.length();
if(len<=1)
return 0;
int pal[][]=new int[len+1][len+1];
int cut[][]=new int[len+1][len+1];
return cut(0,len,s,cut,pal)-1;
}
```