The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. ― Donald E. Knuth

# Algorithms

## 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.