# palindrome partitioningII

## palindrome partitioningII

### DP

`dp[i]`

stand `s.substr(0,i-1)`

's minum cut. dp[i] is the minnum of three values.

`i-1`

`dp[i-1]+1`

`dp[j-1]+1`

substring from j-1 to i-1 is palindrome

```
1 class Solution {
2 public:
3 int minCut(string s) {
4 int l = s.length();
5 int dp[l+1];
6 dp[0] = -1;
7 for ( int i = 1; i <= l; i++ ) {
8 dp[i] = i-1;
9 }
10 for ( int i = 1; i <= l ; i++ ) {
11 int j = min(i,l-i+1)-1;
12 int k = 1;
13 dp[i] = min(dp[i],dp[i-1]+1);
14 while ( k <= j ) {
15 if ( s[i-1-k] == s[i+k-1] ) {
16 dp[i+k] = min(dp[i+k],dp[i-k-1]+1);
17 } else {
18 break;
19 }
20 k++;
21 }
22 j = min(i,l-i)-1;
23 k = 0;
24 while ( k <= j ) {
25 if ( s[i-1-k] == s[i+k] ) {
26 dp[i+k+1] = min(dp[i+k+1],dp[i-k-1]+1);
27 } else {
28 break;
29 }
30 k++;
31 }
32 }
33 return dp[l];
34 }
35 };
```

This solution seems a little hard to undersitand.
`i`

stands for the middle of the palindrome string. `j`

stands for the max length of the left and right of this string. `k`

means the iterative varable.