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
$ C = array_fill ( 0 , $ n , array_fill ( 0 , $ n , NULL ) ) ; $ P = array_fill ( false , $ n , array_fill ( false , $ n , NULL ) ) ;