Palindrome Partitioning | DP | 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 ; Every substring of length 1 is a palindrome ; L is substring length . Build the solution in a 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 the above function
< ? php function minPalPartion ( $ str ) { $ n = strlen ( $ str ) ; $ C = array_fill ( 0 , $ n , array_fill ( 0 , $ n , NULL ) ) ; $ P = array_fill ( false , $ n , array_fill ( false , $ n , NULL ) ) ; 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 ] = PHP_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 ] ; } $ str = " ababbbabbababa " ; echo " Min ▁ cuts ▁ needed ▁ for ▁ Palindrome ▁ Partitioning ▁ is ▁ " . minPalPartion ( $ str ) ; return 0 ; ? >