Pretty confused. C++ O(N^2) DP method always get TLE, please give some help.

• The main idea is using `palindrome[i][j]` array stores the information whether s.substr(i, j - i + 1) is a palindrome string, `cut[i]` array stores the minCut solution of s.substr(i).

I beg the time complexity is O(N^2), but still can't pass the OJ case `aaaaa....aa`.

Finally, I translate the code into `java` and passed... Can anyone give some help?

``````class Solution {
public:
int minCut(string s) {
int N = s.size();
if (N == 0) {
return 0;
}
vector<vector<bool> > palindrome(N, vector<bool>(N, false));
vector<int> cut(N, 0);
for (int start = N - 1; start >= 0; --start) {
cut[start] = N - start - 1;
for (int end = start; end < N; ++end) {
if (s[start] == s[end]) {
palindrome[start][end] = (end - start < 2) ? true : palindrome[start + 1][end - 1];
}
if (palindrome[start][end]) {
if (end == N - 1) {
cut[start] = 0;
}
else {
cut[start] = min(cut[start], cut[end + 1] + 1);
}
}
}
}
return cut[0];
}
};``````

• My plain C solution also runs in `O(N^2)` and fails with TLE. It's far better than `N^2` for most inputs.

I've also found that sometimes my code fails with TLE, but if I resubmit the same code, it is accepted. So it appears the time limits are set very close to the minimum feasible execution time.

All that is to say, the time limits seem to be bogus. Perhaps it is a way to encourage book sales?

• I got the same problem.
Change

``````vector<vector<bool> > palindrome(N, vector<bool>(N, false));
``````

to

``````bool palindrome[N][N];
``````

might works.

But I still don't know why a vector can cause LTE while array can pass easily.

Can someone help?

Following is my code. if I use vector it cause LTE. if I use array it passed with 21ms. STRANGE!

``````class Solution {
public:
int minCut(string s) {
int l=s.length();
//vector<vector<bool>> dp(l,vector<bool>(l,1));
bool dp[l][l];
for(int j=0;j<l;j++){
for(int i=0;i+j<l;i++)
dp[i][i+j]=(j<2||dp[i+1][i+j-1])&&(s[i]==s[i+j]);
}
if(dp[0][l-1]) return 0;
int cut[l];
cut[0]=0;
for(int i=1;i<l;i++){
if(dp[0][i]) cut[i]=0;
else{
cut[i]=l;
for(int j=0;j<i;j++)
if(dp[j+1][i]&&cut[i]>cut[j]+1) cut[i]=cut[j]+1;
}
}
return cut[l-1];
}
};
``````

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