```
class Solution {
public:
int minCut(string s) {
if(s=="") return 0;
int sz = s.size(), i = 0;
vector<int> dp(sz+1,INT_MAX);
dp[0] = 0;
while(i<sz){
int j = i;
while(j+1<sz&&s[j+1]==s[i]) j++;
for(int k = i; k <=j; k ++){
for(int m = k; m <=j; m++){
dp[m+1] = min(dp[m+1], dp[k]+1);
}
}
int l = i-1, r = j+1;
while(l>=0&&r<sz&&s[l]==s[r]) {
r++;
dp[r] = min(dp[r], dp[l--]+1);
}
i = j+1;
}
return dp[sz]-1;
}
};
```

- Use
**dp[i]** (i>0) to record minimal palindrome partitions of substring 0 to i-1.
- From middle to two sides to find a palindrome, which is more efficient. Once find a palindrome, update
**dp**.