Minimum Cost to make two Numeric Strings Identical | C # 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
using System ; public class GFG { static int lcs ( int [ , ] dp , 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 = ( a [ m ] - 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 ; } static int costOfString ( String str ) { int cost = 0 ; for ( int i = 0 ; i < str . Length ; i ++ ) cost += ( str [ i ] - 48 ) ; return cost ; } public static void Main ( ) { String a , b ; a = "9142" ; b = "1429" ; int [ , ] dp = new int [ 101 , 101 ] ; Console . Write ( ( costOfString ( a ) + costOfString ( b ) - 2 * lcs ( dp , a , b , a . Length - 1 , b . Length - 1 ) ) ) ; } }