# 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.