Minimum cost to make Longest Common Subsequence of length k | Java program to find subarray with sum closest to 0 ; Return Minimum cost to make LCS of length k ; If k is 0. ; If length become less than 0 , return big number . ; If state already calculated . ; Finding the cost ; Finding minimum cost and saving the state value ; Driver code
using System ; class GFG { static int N = 30 ; static int solve ( char X [ ] , char Y [ ] , int l , int r , int k , int dp [ ] [ ] [ ] ) { if ( k == 0 ) { return 0 ; } if ( l < 0 r < 0 ) { return ( int ) 1e9 ; } if ( dp [ l ] [ r ] [ k ] != - 1 ) { return dp [ l ] [ r ] [ k ] ; } int cost = ( X [ l ] - ' a ' ) ^ ( Y [ r ] - ' a ' ) ; return dp [ l ] [ r ] [ k ] = Math . min ( Math . min ( cost + solve ( X , Y , l - 1 , r - 1 , k - 1 , dp ) , solve ( X , Y , l - 1 , r , k , dp ) ) , solve ( X , Y , l , r - 1 , k , dp ) ) ; } public static void main ( String [ ] args ) { char X [ ] = " abble " . toCharArray ( ) ; char Y [ ] = " pie " . toCharArray ( ) ; int n = X . length ; int m = Y . length ; int k = 2 ; int [ ] [ ] [ ] dp = new int [ N ] [ N ] [ N ] ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) { for ( int l = 0 ; l < N ; l ++ ) { dp [ i ] [ j ] [ l ] = - 1 ; } } } int ans = solve ( X , Y , n - 1 , m - 1 , k , dp ) ; System . out . println ( ans == 1e9 ? - 1 : ans ) ; } }