# My 35ms O(n^2) DP with O(n) space

• ``````class Solution {
public:
int minCut(string s) {
// the state is 1-based
vector<int> palindrome_numbers(s.size() + 1);
fill(palindrome_numbers.begin(), palindrome_numbers.end(), -1);
palindrome_numbers[0] = 0;

init(s);

for (int i = 1; i <= s.size(); i++) {
for (int j = 0; j < i; j++ ) {
if (palindrome_numbers[j] != -1 && is_palindrome(j + 1, i)) {
if (palindrome_numbers[i] == -1)
palindrome_numbers[i] = palindrome_numbers[j] + 1;
else
palindrome_numbers[i] = min(palindrome_numbers[i], palindrome_numbers[j] + 1);
}
}
}
return palindrome_numbers[s.size()]-1;
}
private:

vector<int> span;

void init(const string &s) {
span.resize(s.size() * 2);
for (int i = 0; i < s.size(); i++) {
int a = i , b = i;
span[a + b] = calc_span(s, a, b);
if (i != s.size() - 1) {
int a = i, b = i + 1;
span[a + b] = calc_span(s, a, b);
}
}
}

int calc_span(const string &s, int a, int b) {
while (a >= 0 && b < s.size() && s[a] == s[b]) a--, b++;
return b - 1 - (a + 1);
}

// [a, b]
bool is_palindrome(int a, int b) {
//change 1-based to 0-based;
a--, b--;
return span[a + b] >= b - a;
}
};``````

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