# Why my O(n^2) DP solution always get TLE for long input

• Basic idea: Using a vector of vector vvi to record all the possible palindrome position, for example, vvi[i] is not empty only when there is a palindrome starting from s[i] and the element of vvi[i] records all the next possible palindrome starting positions. Vector dp[] is used to store the min cut for sub string s[i,...,n-1]. With the table vvi, one could scan from right of vvi to left to obtain all the element of dp[], output is dp[0];

Can anyone help me to improve it? Thanks!

``````    int minCut(string s) {
int n=s.size();
if(s.size()==1) return 0;
if(setTable(s)) return 0;
vector<int> dp(n);// dp[i] store the minCut for s[i...n-1]
dp[n-1]=0;
for(int i=n-2; i>=0;i--){
dp[i]=n-i-1;
for(auto it=vvi[i].begin();it!=vvi[i].end();it++){
if(*it==n) dp[i]=0;
if(dp[*it]+1<dp[i]) dp[i]=dp[*it]+1;
}
}
return dp[0];
}
int setTable(string s){ // set up a table vvi such that vvi[i] record all the next Palindrome start position.
int n=s.size();
vvi.resize(n);
for(int i=n-1;i>=0;i--){ // first search how many positions could arrive at the end of s;
if(isPalindrome(s.substr(i))) vvi[i].push_back(n);
}

if(!vvi[0].empty() && vvi[0][0]==n) return 0; //if we there is a palindrome starting 0, then the cut is 0;
for(int i=s.size()-1;i>=0;i--){
if(!vvi[i].empty()){ //if vvi[i] is not empty then start searching all palindromes ended at s[i-1].
for(int j=i-1;j>=0;j--){
if(isPalindrome(s.substr(j,i-j))) vvi[j].push_back(i); //found one mark vvi[j] with i.
}
}
}
return 1;
}
bool isPalindrome(string s){
if(s.size()==1) return true;
for(int i=0,j=s.size()-1;i<j;i++,j--){
if(s[i]!=s[j]) return false;
}
return true;
}``````

• your isPalindrome function brings another O(n) in, so in total you algorithm is O(n^3) instead of O(n^2). My first submission is similar to yours.

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