Minimum Cost to make two Numeric Strings Identical | Function to find weight of LCS ; if this state is already calculated then return ; adding required weight for particular match ; recurse for left and right child and store the max ; Function to calculate cost of string ; Driver code ; Minimum cost needed to make two strings identical
function lcs ( dp , a , b , m , n ) { if ( m < 0 n < 0 ) { return 0 ; } if ( dp [ m ] [ n ] != - 1 ) return dp [ m ] [ n ] ; let ans = 0 ; if ( a [ m ] == b [ n ] ) { ans = ( a [ m ] . charCodeAt ( 0 ) - 48 ) + lcs ( dp , a , b , m - 1 , n - 1 ) ; } else ans = Math . max ( lcs ( dp , a , b , m - 1 , n ) , lcs ( dp , a , b , m , n - 1 ) ) ; dp [ m ] [ n ] = ans ; return ans ; } function costOfString ( str ) { let cost = 0 ; for ( let i = 0 ; i < str . length ; i ++ ) cost += ( str [ i ] . charCodeAt ( 0 ) - 48 ) ; return cost ; } let a = " " ; let b = " " ; let dp = new Array ( 101 ) ; for ( let i = 0 ; i < dp . length ; i ++ ) { dp [ i ] = new Array ( 101 ) ; for ( let j = 0 ; j < 101 ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } document . write ( ( costOfString ( a ) + costOfString ( b ) - 2 * lcs ( dp , a , b , a . length - 1 , b . length - 1 ) ) ) ;