text: Palindrome Partitioning | DP | Dynamic Programming Solution for Palindrome Partitioning Problem ; Returns the minimum number of cuts needed to partition a string such that every part is a palindrome ; Get the length of the string ; Create two arrays to build the solution in bottom up manner C [ i ] [ j ] = Minimum number of cuts needed for palindrome partitioning of substring str [ i . . j ] P [ i ] [ j ] = true if substring str [ i . . j ] is palindrome , else false Note that C [ i ] [ j ] is 0 if P [ i ] [ j ] is true ; different looping variables ; Every substring of length 1 is a palindrome ; L is substring length . Build the solution in bottom up manner by considering all substrings of length starting from 2 to n . The loop structure is same as Matrix Chain Multiplication problem ( See https : www . geeksforgeeks . org / matrix - chain - multiplication - dp - 8 / ) ; For substring of length L , set different possible starting indexes ; Set ending index ; If L is 2 , then we just need to compare two characters . Else need to check two corner characters and value of P [ i + 1 ] [ j - 1 ] ; IF str [ i . . j ] is palindrome , then C [ i ] [ j ] is 0 ; Make a cut at every possible location starting from i to j , and get the minimum cost cut . ; Return the min cut value for complete string . i . e . , str [ 0. . n - 1 ] ; Driver program to test above function
code: #include <limits.h> NEW_LINE #include <stdio.h> NEW_LINE #include <string.h> NEW_LINE int min ( int a , int b ) { return ( a < b ) ? a : b ; } int minPalPartion ( char * str ) { int n = strlen ( str ) ; int C [ n ] [ n ] ; bool P [ n ] [ n ] ; int i , j , k , L ; for ( i = 0 ; i < n ; i ++ ) { P [ i ] [ i ] = true ; C [ i ] [ i ] = 0 ; } for ( L = 2 ; L <= n ; L ++ ) { for ( i = 0 ; i < n - L + 1 ; i ++ ) { j = i + L - 1 ; if ( L == 2 ) P [ i ] [ j ] = ( str [ i ] == str [ j ] ) ; else P [ i ] [ j ] = ( str [ i ] == str [ j ] ) && P [ i + 1 ] [ j - 1 ] ; if ( P [ i ] [ j ] == true ) C [ i ] [ j ] = 0 ; else { C [ i ] [ j ] = INT_MAX ; for ( k = i ; k <= j - 1 ; k ++ ) C [ i ] [ j ] = min ( C [ i ] [ j ] , C [ i ] [ k ] + C [ k + 1 ] [ j ] + 1 ) ; } } } return C [ 0 ] [ n - 1 ] ; } int main ( ) { char str [ ] = " ababbbabbababa " ; printf ( " Min ▁ cuts ▁ needed ▁ for ▁ Palindrome ▁ Partitioning ▁ is ▁ % d " , minPalPartion ( str ) ) ; return 0 ; }