the first version implementation

the key idea is to calculate the cut[i], and of course, at first, I want to use

```
dp[i][j] refers to the min-cut needed for s[i...j]
closed field s[i,j]
```

But I failed to figure out how to write the implementable equations.

So I referred to the top voted post. As you can see,

They set that

```
cut[i] refers to the min-cut needed for s[0..i-1]
open filed s[0,i) means s[0, i-1]
```

So the equation would be like this

```
cut[i] = min{ cut[j]+1 if s[j...i] is palindrome } s.t. j<=i
```

The coding key points is as :

```
-1- inilize the cut[i] = i-1;
-2- when dp[i][j] we can update the cut[i] = min(cut[i], cut[j]+1)
```

Code

```
class Solution {
public:
int minCut(string s) {
/***
* cut[i] = min{ cut[j] + 1 }
* s.t. dp[j][i]=true which means s[j..i ] is palindrome
* cut[i] means the min-cut needed for s[0...i]
***/
int len=s.size();
vector<vector<bool>> dp(len, vector<bool>(len, false));
vector<int> cut(len+1);
for(int i=0; i<len; i++) dp[i][i]=true;
for(int i=0; i<=len; i++) cut[i]=i-1;
for(int i=0; i<len; i++){
for(int j=0; j<=i; j++){
if(i-j<=1)
dp[j][i]=(s[i]==s[j]);
else
dp[j][i]=(s[i]==s[j]) && dp[j+1][i-1];
if(dp[j][i])
cut[i+1]=min(cut[i+1], cut[j]+1);
}
}
return cut[len];
}
};
```