Minimum Cost to make two Numeric Strings Identical | CPP program to find 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; typedef long long int ll ; int lcs ( int dp [ 101 ] [ 101 ] , string a , string b , int m , int n ) { for ( int i = 0 ; i < 100 ; i ++ ) for ( int j = 0 ; j < 100 ; j ++ ) dp [ i ] [ j ] = -1 ; if ( m < 0 n < 0 ) { return 0 ; } if ( dp [ m ] [ n ] != -1 ) return dp [ m ] [ n ] ; int ans = 0 ; if ( a [ m ] == b [ n ] ) { ans = int ( a [ m ] - 48 ) + lcs ( dp , a , b , m - 1 , n - 1 ) ; } else ans = max ( lcs ( dp , a , b , m - 1 , n ) , lcs ( dp , a , b , m , n - 1 ) ) ; dp [ m ] [ n ] = ans ; return ans ; } int costOfString ( string str ) { int cost = 0 ; for ( int i = 0 ; i < str . length ( ) ; i ++ ) cost += int ( str [ i ] - 48 ) ; return cost ; } int main ( ) { string a , b ; a = "9142" ; b = "1429" ; int dp [ 101 ] [ 101 ] ; cout << ( costOfString ( a ) + costOfString ( b ) - 2 * lcs ( dp , a , b , a . length ( ) - 1 , b . length ( ) - 1 ) ) ; return 0 ; }