Minimum cost to make two strings identical by deleting the digits | Function to returns cost of removing the identical characters in LCS for X [ 0. . m - 1 ] , Y [ 0. . n - 1 ] ; Following steps build L [ m + 1 ] [ n + 1 ] in bottom up fashion . Note that L [ i ] [ j ] contains cost of removing identical characters in LCS of X [ 0. . i - 1 ] and Y [ 0. . j - 1 ] ; If both characters are same , add both of them ; Otherwise find the maximum cost among them ; Returns cost of making X [ ] and Y [ ] identical ; Find LCS of X [ ] and Y [ ] ; Initialize the cost variable ; Find cost of all characters in both strings ; Driver code
< ? php function lcs ( $ X , $ Y , $ m , $ n ) { $ L = array ( $ m + 1 , $ n + 1 ) ; for ( $ i = 0 ; $ i <= $ m ; ++ $ i ) { for ( $ j = 0 ; $ j <= $ n ; $ j ++ ) { if ( $ i == 0 $ j == 0 ) $ L [ $ i ] [ $ j ] = 0 ; else if ( $ X [ $ i - 1 ] == $ Y [ $ j - 1 ] ) $ L [ $ i ] [ $ j ] = $ L [ $ i - 1 ] [ $ j - 1 ] + 2 * ( $ X [ $ i - 1 ] - '0' ) ; else $ L [ $ i ] [ $ j ] = $ L [ $ i - 1 ] [ $ j ] > $ L [ $ i ] [ $ j - 1 ] ? $ L [ $ i - 1 ] [ $ j ] : $ L [ $ i ] [ $ j - 1 ] ; } } return $ L [ $ m ] [ $ n ] ; } function findMinCost ( $ X , $ Y ) { $ m = sizeof ( $ X ) ; $ n = sizeof ( $ Y ) ; $ cost = 0 ; for ( $ i = 0 ; $ i < $ m ; ++ $ i ) $ cost += $ X [ $ i ] - '0' ; for ( $ i = 0 ; $ i < $ n ; ++ $ i ) $ cost += $ Y [ $ i ] - '0' ; return $ cost - lcs ( $ X , $ Y , $ m , $ n ) ; } $ X = str_split ( "3759" ) ; $ Y = str_split ( "9350" ) ; echo ( " Minimum ▁ Cost ▁ to ▁ make ▁ two ▁ strings " . " identical is = "