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];
}
};
```