# [recommend for beginners]clean C++ implementation

• 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];
}
};``````

• In fact, I do think the most top-voted answer is too tricky. It is not easy to think and implement it with no bug. I do think almost non-of-the-voters can implement it with out looking at this post. I do think the key idea behind the implementation is that it want to save the palindrome check cost.

So it just use loop to calculate the all-the-possible-palindrome-length and update the cut based on it.

Code

``````  class Solution {
public:
int minCut(string s) {
int n=s.size();
vector<int> cut(n+1);
for(int i=0; i<=n; i++)  cut[i]=i-1;
for(int i=0; i<n; i++){
for(int j=0; i-j>=0&&i+j<n&&s[i-j]==s[i+j]; j++)
cut[i+j+1]=min(cut[i+j+1], 1+cut[i-j]);
for(int j=1; i-j+1>=0&&i+j<n&&s[i-j+1]==s[i+j]; j++)
cut[i+j+1]=min(cut[i+j+1], 1+cut[i-j+1]);
}
return cut[n];
}
};``````

• 2 times AC solution

``````class Solution {
public:
int minCut(string s) {
int size_s = s.size();
vector<vector<bool>> dp(size_s, vector<bool>(size_s, false));
for(int i= 0; i < size_s; i++)  dp[i][i] = true;
vector<int> cut(size_s + 1, 0);
for(int i = 0; i <= size_s; i++)  cut[i] = i - 1;

for(int i = 1; i < size_s; i++) {
for(int j = 0; j <= i; j++){
if(i-j <= 1){
dp[j][i] = (s[j]==s[i]);
}
else{
dp[j][i] = (s[j]==s[i] && dp[j+1][i-1]);
}

if(dp[j][i]) {
cut[i+1] = min(cut[i+1], cut[j] + 1);
}
}
}
return cut[size_s];
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.