[C++] Bottom-Up DP, O(n2)

#1

Bottom up dynamic programming solution… O(n2)

bool is_palindrome(string& s, int left, int right) {
    while (left < right && s[left] == s[right])
        left++, right--;
    return left >= right;
}

int cuts[1000000];
long long compute(string& A, int index) {
    if (index == A.size())
        return 0;

    if (cuts[index] != -1)
        return cuts[index];

    long long result = INT_MAX;
    for (int i=index; i<A.size(); i++)
        if (is_palindrome(A, index, i)) // Break only if you find a palindrome
            result = min(result, 1 + compute(A, i+1));

    cuts[index] = result;
    return result;
}

int Solution::minCut(string A) {
    for (int i=0; i<=A.size(); i++)
        cuts[i] = -1;
    return compute(A, 0) - 1;
}