Minimum cost to make Longest Common Subsequence of length k | Python3 program to calculate Minimum cost to make Longest Common Subsequence of length k ; 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 cost ;  ; Driver Code
N = 30 NEW_LINE def solve ( X , Y , l , r , k , dp ) : NEW_LINE INDENT if k == 0 : NEW_LINE INDENT return 0 NEW_LINE DEDENT if l < 0 or r < 0 : NEW_LINE INDENT return 1000000000 NEW_LINE DEDENT if dp [ l ] [ r ] [ k ] != - 1 : NEW_LINE INDENT return dp [ l ] [ r ] [ k ] NEW_LINE DEDENT cost = ( ( ord ( X [ l ] ) - ord ( ' a ' ) ) ^ ( ord ( Y [ r ] ) - ord ( ' a ' ) ) ) NEW_LINE DEDENT / * Finding minimum cost and saving the state value * / NEW_LINE INDENT dp [ l ] [ r ] [ k ] = 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 ) ] ) NEW_LINE return dp [ l ] [ r ] [ k ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT X = " abble " NEW_LINE Y = " pie " NEW_LINE n = len ( X ) NEW_LINE m = len ( Y ) NEW_LINE k = 2 NEW_LINE dp = [ [ [ - 1 ] * N for __ in range ( N ) ] for ___ in range ( N ) ] NEW_LINE ans = solve ( X , Y , n - 1 , m - 1 , k , dp ) NEW_LINE print ( - 1 if ans == 1000000000 else ans ) NEW_LINE DEDENT