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
def lcs ( dp , a , b , m , n ) : NEW_LINE INDENT for i in range ( 100 ) : NEW_LINE INDENT for j in range ( 100 ) : NEW_LINE INDENT dp [ i ] [ j ] = - 1 NEW_LINE DEDENT DEDENT if ( m < 0 or n < 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( dp [ m ] [ n ] != - 1 ) : NEW_LINE INDENT return dp [ m ] [ n ] NEW_LINE DEDENT ans = 0 NEW_LINE if ( a [ m ] == b [ n ] ) : NEW_LINE INDENT ans = ( ord ( a [ m ] ) - 48 ) + lcs ( dp , a , b , m - 1 , n - 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT ans = max ( lcs ( dp , a , b , m - 1 , n ) , lcs ( dp , a , b , m , n - 1 ) ) NEW_LINE DEDENT dp [ m ] [ n ] = ans NEW_LINE return ans NEW_LINE DEDENT def costOfString ( s ) : NEW_LINE INDENT cost = 0 NEW_LINE for i in range ( len ( s ) ) : NEW_LINE INDENT cost += ( ord ( s [ i ] ) - 48 ) NEW_LINE DEDENT return cost NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = "9142" NEW_LINE b = "1429" NEW_LINE dp = [ [ 0 for x in range ( 101 ) ] for y in range ( 101 ) ] NEW_LINE print ( costOfString ( a ) + costOfString ( b ) - 2 * lcs ( dp , a , b , len ( a ) - 1 , len ( b ) - 1 ) ) NEW_LINE DEDENT