Minimum steps to delete a string after repeated deletion of palindrome substrings | method returns minimum step for deleting the string , where in one step a palindrome is removed ; declare dp array and initialize it with 0 s ; loop for substring length we are considering ; loop with two variables i and j , denoting starting and ending of substrings ; If substring length is 1 , then 1 step will be needed ; delete the ith char individually and assign result for subproblem ( i + 1 , j ) ; if current and next char are same , choose min from current and subproblem ( i + 2 , j ) ; loop over all right characters and suppose Kth char is same as ith character then choose minimum from current and two substring after ignoring ith and Kth char ; Uncomment below snippet to print actual dp tablex for ( int i = 0 ; i < N ; i ++ , cout << endl ) for ( int j = 0 ; j < N ; j ++ ) cout << dp [ i ] [ j ] << " ▁ " ; ; Driver code
< ? php function minStepToDeleteString ( $ str ) { $ N = strlen ( $ str ) ; $ dp [ $ N + 1 ] [ $ N + 1 ] = array ( array ( ) ) ; for ( $ i = 0 ; $ i <= $ N ; $ i ++ ) for ( $ j = 0 ; $ j <= $ N ; $ j ++ ) $ dp [ $ i ] [ $ j ] = 0 ; for ( $ len = 1 ; $ len <= $ N ; $ len ++ ) { for ( $ i = 0 , $ j = $ len - 1 ; $ j < $ N ; $ i ++ , $ j ++ ) { if ( $ len == 1 ) $ dp [ $ i ] [ $ j ] = 1 ; else { $ dp [ $ i ] [ $ j ] = 1 + $ dp [ $ i + 1 ] [ $ j ] ; if ( $ str [ $ i ] == $ str [ $ i + 1 ] ) $ dp [ $ i ] [ $ j ] = min ( 1 + $ dp [ $ i + 2 ] [ $ j ] , $ dp [ $ i ] [ $ j ] ) ; for ( $ K = $ i + 2 ; $ K <= $ j ; $ K ++ ) if ( $ str [ $ i ] == $ str [ $ K ] ) $ dp [ $ i ] [ $ j ] = min ( $ dp [ $ i + 1 ] [ $ K - 1 ] + $ dp [ $ K + 1 ] [ $ j ] , $ dp [ $ i ] [ $ j ] ) ; } } } return $ dp [ 0 ] [ $ N - 1 ] ; } $ str = "2553432" ; echo minStepToDeleteString ( $ str ) , " STRNEWLINE " ; ? >