Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Leetcode 132: Palindrome Partitioning II (recursive DP)
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.