Python solution: Recursive top-down DP + memoization


#1
# To overcome stack size issue for recursion
import sys
sys.setrecursionlimit(10**6)


class Solution:
    # @param A : string
    # @param B : string
    # @return an integer
    
    # if for some (i, j) A[i] = B[j], then one of the possible longest common subsequence 
    # can be Longest common subsequence of
    # (A[1..i-1], B[1....j-1]) + A[i] + Longest commen subsequence of
    # (A[i+1....n], B[j+1....m])
    
    # Recursion relation can be written as:-

    # LCS(A[1.....i], B[1........j]) = 
    #     maximum (LCS(A[1.....i-1], B[1.....j-1] + 1,       //if(A[i] = B[j])
    #              LCS(A[1.....i-1], B[1.....j] ,
    #              LCS(A[1.....i], B[1.....j-1] )
    
    # https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

    def lcs(self, A, B, i, j, d):

        if i < 0 or j < 0:
            return 0
            
        # memoization: retrieve already calculated data from the dict
        if d.get('{}_{}'.format(i, j)):
            return d.get('{}_{}'.format(i, j))

        result = max(
            self.lcs(A, B, i-1, j-1, d) + 1 if A[i] == B[j] else 0,
            self.lcs(A, B, i-1, j, d),
            self.lcs(A, B, i, j-1, d)
            )
            
        # memoization: save calculated data for the next times
        d['{}_{}'.format(i, j)] = result
        
        return result

    def solve(self, A, B):
        
        return self.lcs(A, B, len(A) - 1, len(B) - 1, {})