#### Dynamic Programming

Problem
Splitting a String into minimum number of palindromes.
Given a string, find the minimum no. of palidromes into which the string can be broken.
Consider the string “civic” ( String is Palindrome by itself, so min no. of palindromes = 1 )
The string “abcde” cannot be splitted into less than 5 palindromes ( each character is a palindrome )
Consider the string “civicacaramanamaracacammacdeified”.
It can be broken into 4 palindromes ” civic ” + ” acaramanamaraca ” + ” cammac ” + ” deified “

Solution
Suppose the size of the string is n.
We maintain a 2D array palins [ n ][ n ] where palins [ i ][ j ] stores the minimum number of palindromes in the string str [ i … j ] i.e from index ‘ i ‘ to index ‘ j ‘ of the string. So, the final solution of breaking the string of size n into minimum no. of palindromes is given by palins [ 0 ][ n – 1 ].
Let us determine the structure of the optimal solution.
Let palins ( i , j ) denotes the min no. of palindromes in the string str ( i … j ).
We will try to break the string at all possible positions k such that i <= k < j and sum up the minimum no. of palindromes in palins ( i , k ) and palins ( k , j ).
Thus, the structure of optimal solution is determined recursively as :
palins ( i , j ) = palins ( i , k ) + palins ( k , j ) for all i <= k < j
Finally, palins ( 0 , n – 1 ) gives the required solution. See the implementation below.

```#include<iostream>
#include<cstring>
using namespace std;

// check if a string is palindrome, given the start and end index of the string
bool isPalindrome(char str[], int i, int j) {
while (i < j) {
if (str[i++] != str[j--])
return false;
}
return true;
}

/* Find the minimum no. of palindromes in the input string i.e the
string has to broken down into min. no. of palindromes
Suppose palins[i][j] -> min no. of palindromes in the string str[i...j]
Then, palins[0][n-1] is the final solution
Standard Recursive Solution :-
palins(i,j) = min(palins(i,k) + palins(k,j)) for i <= k < j
*/
int minPalindromes(char str[]) {
int i, j, k;
int substr_size; //substring size
int n = strlen(str);
// Matrix where cell (i,j) stores the minimum no. of palindromes in str[i...j]
int palins[n][n];

// iterating over all possible substring sizes
for (substr_size = 1; substr_size <= n; substr_size++) {
// 'i' and 'j' tracks the start and end index of the current substring
for (i = 0; i <= n - substr_size; i++) {
j = i + substr_size - 1;
if (isPalindrome(str, i, j)) {
// substring is a palindrome
palins[i][j] = 1;
}
else {
// search for palindromes within the substring
// worst case (min. no of palindromes = length of the substring)
// each character is a palindrome
palins[i][j] = substr_size;
// find min no. of palindromes within substring
for (k = i; k < j; k++) {
// try splitting substring at each position
int sum = palins[i][k] + palins[k+1][j];
if (sum < palins[i][j])
palins[i][j] = sum;
}
}
}
}
// return min no. of palindromes in the input string
return palins[0][n-1];
}

// main
int main() {
char str[] = "civicacaramanamaracacammacdeified";
//civic + acaramanamaraca + cammac + deified (4 palindromes)
int min_palin = minPalindromes(str);
cout<<"\nMinimum no. of palindromes :: "<<min_palin;
cout<<endl;
return 0;
}```