Leetcode 132: Palindrome Partitioning II (recursive DP)

leetcode_132b.cpp

#include <iostream>
#include <string>
#include <vector>

using namespace std;

void calcPalindromes(const string& s, vector<vector<bool>>& dp) {
    for (int i=s.size()-1; i >= 0; --i) {
        for (int j=i; j<s.size(); ++j) {
            if (i==j) dp[i][j]=true;
            else if (s[i] == s[j]) {
                if (j-i == 1) dp[i][j] = true;
                else dp[i][j] = dp[i+1][j-1];
            }
            else dp[i][j] = false;
        }
    }
}

int getMinCuts(const string& s, int start, int end, const vector<vector<bool>>& dpPal, vector<vector<int>>& dpCuts) {
    if (end-start == 0 || dpPal[start][end]) return 0;

    if (dpCuts[start][end] != -1) return dpCuts[start][end];
    for (int i=start+1; i<=end; ++i) {
        int cuts = 1 + getMinCuts(s, start, i-1, dpPal, dpCuts) + getMinCuts(s, i, end, dpPal, dpCuts);
        if (dpCuts[start][end] == -1 || cuts < dpCuts[start][end]) dpCuts[start][end] = cuts;
    }
    return dpCuts[start][end];
}

int minCut(string s) {
    vector<vector<bool>> dpPal(s.size(), vector<bool>(s.size(), false));
    vector<vector<int>> dpCuts(s.size(), vector<int>(s.size(), -1));
    calcPalindromes(s, dpPal);
    return getMinCuts(s, 0, s.size()-1, dpPal, dpCuts);
}

int main() {
    //string s = "eegiicgaeadbcfacfhifdbiehbgejcaeggcgbahfcajfhjjdgj"; //"abcd";
    string s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
    cout << minCut(s) << "\n";
    return 0;
}