Palindrome Partitioning Min Cuts

• Time : O(n^2)
• Space : O(n^2)

c++

#include <vector>
using namespace std;
bool palindrome(string& s, int l, int r) {
	while(l < r) {
		if(s[l++] != s[r--]) return false;
	}
	return true;
}

int helper(string& s, vector<vector<int>>& dp, int l, int r) {
	if(l >= r) return 0;
	if(dp[l][r] != -1) return dp[l][r];
	dp[l][r] = r - l + 1;
	if(palindrome(s,l,r)) dp[l][r] = 0;
	else {
		for(int i = l; i < r; i++) {
			if(palindrome(s, l, i)) {
				dp[l][r] = min(dp[l][r], 1 + helper(s, dp, i + 1, r));
			}
		}
	}
	
	return dp[l][r];
}

int palindromePartitioningMinCuts(string string) {
  int n = string.length();
	vector<vector<int>> dp(n, vector<int>(n, -1));
	
  return helper(string, dp, 0, n - 1);
}