# How can I boost my program to O^2?

• my following program is running in O(n^3), and always get TLE

``````public int minPalPartition2(String s){
if(s==null) return -1;
char[] str = s.toCharArray();
int length = str.length;
int[][] minCut= new int[length][length];
boolean[][] isPal = new boolean[length][length];
for(int i=0;i<length;i++){
isPal[i][i]=true;
minCut[i][i]=0;
}
for(int i=0;i<length;i++){
for(int j=i+1;j<length;j++){
int subLength = j-i+1;
if(subLength==2)
isPal[i][j] = str[i]==str[j];
else
isPal[i][j] = (str[i]==str[j]&&isPal[i+1][j-1]);
if(isPal[i][j]==true)
minCut[j][j]=0;
else{
minCut[i][j]=Integer.MAX_VALUE;
for(int k=i;k<j;k++){
minCut[i][j]=Math.min(minCut[i][j],minCut[i][k]+1+minCut[k+1][j]);
}
}
}
}
return minCut[0][length-1];
}``````

• If you want O(n^2). you could think this:　dp(i) = min( dp(j) + 1 ) for all j < i that isPal(j + 1, i); And you could calculate isPal before DP by O(n^2) as your code did. As a result, you only need O(n^2) to do DP. And dp(s.length()) is the final answer.

• I think there is something wrong with your calculation of isPal[i][j]. You cannot make sure that isPal[i+1][j-1] is calculated before calculating isPal[i][j]. The loop condition needs change.

• Here is an elegant DP solution, where dp[i] means min cut(+1) for the prefix of s with length i. The transition is natural for the monotonic property of palindrome strings. The p controls even/odd palindromes.

``````class Solution {
public:
int minCut(string s) {
int N = s.size();
vector<int> dp(N+1,numeric_limits<int>::max());
dp[0] = 0;
for(int i=0;i<N;i++)
for(int p=0;p<=1;p++)
for(int l=0;l<=N;l++) {
int a=i-l, b = i+l+p;
if( a < 0 || b >= N || s[a]!=s[b] )
break;
dp[b+1] = min(dp[b+1],dp[a]+1);
}
return dp[N]-1;
}
};``````

• This code is a little difficult to understand, which is really elegant.
Note that i is the centre of a PAL string.
and the L loop uses the previous comparation which is very useful to avoid time consuming.

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