Iâ€™m not sure why youâ€™re getting TLE. It looks like your code is \mathcal O(n^2). Did you try a bottom up approach?

Here is my \mathcal O(n^2) implementation, but with a 1D dp.

##
Code

```
class Solution {
public:
int minCut(string s) {
int n = s.size();
vector<vector<bool>> ispal(n, vector<bool>(n));
for(int i = 0; i < n; i++) ispal[i][i] = 1;
for(int i = 1; i < n; i++) ispal[i][i - 1] = 1;
for(int p = 1; p < n; p++) {
for(int i = 0; i < n - p; i++) {
int j = i + p;
if(s[i] == s[j]) ispal[i][j] = ispal[i + 1][j - 1];
}
}
vector<int> dp(n, INT_MAX);
for(int i = 0; i < n; i++) {
for(int j = 0; j <= i; j++) {
if(ispal[j][i]) {
if(j == 0)
dp[i] = min(dp[i], 0);
else
dp[i] = min(dp[i], 1 + dp[j - 1]);
}
}
}
return dp[n-1];
}
};
```