Palindrome Partitioning I I Algorithm

The Palindrome Partitioning II Algorithm is a dynamic programming approach that aims to solve the problem of partitioning a given string into the minimum number of palindrome substrings. A palindrome is a word, phrase, number, or other sequences of characters that reads the same forward and backward (ignoring spaces, punctuation, and capitalization). In this algorithm, the primary goal is to find the least number of cuts required to partition the given string in such a way that every partition is a palindrome. The algorithm employs a two-dimensional table to store the palindromic information of the substrings and a one-dimensional table to store the minimum cuts for each index of the string. The two-dimensional table is filled using a nested loop that iterates through the entire string and checks if the substrings are palindromes or not. If a palindrome is found, the respective entries in the table are updated accordingly. Simultaneously, the cuts table is updated by comparing the current minimum cuts with a new cut that can be made at the current palindrome. By the end of the algorithm, the last entry in the cuts table represents the minimum number of cuts required to partition the given string into palindromes.
const int MAXN = 2010;
const int INFS = 0x3fffffff;

class Solution {
public:
	int minCut(string s) {
		// Start typing your C/C++ solution below
		// DO NOT write int main() function
		
		int n = s.size();
		memset(dp, false, sizeof(dp));
		for (int i = 0; i < n; i++)
			dp[i+1][i] = dp[i][i] = true;
		for (int d = 1; d < n; d++)
			for (int i = 0, j = i+d; j < n; i++, j++)
				if (s[i] == s[j]) 
					dp[i][j] |= dp[i+1][j-1];
		for (int i = 0; i < n; i++)
			F[i] = INFS;
		F[0] = 0;
		for (int i = 1; i < n; i++)
			for (int j = 0; j < i; j++)
				if (dp[0][i])
					F[i] = 0;
				else if (dp[j+1][i])
					F[i] = min(F[i], F[j] + 1);
		return F[n-1];

	}
private:
	bool dp[MAXN][MAXN];
	int F[MAXN];
};

LANGUAGE:

DARK MODE: