class Solution:
    def longestCommonSubsequence(self, n: str, m: str) -> int:
        memo = [[0 for j in range(len(m))] for i in range(len(n))]
        def lcs(i,j):
            if i == len(n) or  j == len(m):
                return 0
            if memo[i][j]:
                return memo[i][j]
            if n[i] == m[j]:
                memo[i][j] = 1 + lcs(i+1,j+1)
            else:
                memo[i][j] = max(lcs(i,j+1),lcs(i+1,j))
            return memo[i][j]
        return lcs(0,0)
	```
	
	
	Dynamic Programming (600ms)
	```
	class Solution:
    def longestCommonSubsequence(self, s1: str, s2: str) -> int:
        arr = [[0 for i in range(len(s2))] for j in range(len(s1))]
        maxi = 0
        for i in range(len(s1)):
            if s1[i] == s2[0]:
                arr[i][0] = 1
                maxi = 1
            else:
                if i!=0:
                    arr[i][0] = arr[i-1][0]
        for i in range(len(s2)):
            if s2[i] == s1[0]:
                arr[0][i] = 1 
                maxi = 1
            else:
                if i!=0:
                    arr[0][i] = arr[0][i-1]
        
        for i in range(1,len(s1)):
            for j in range(1,len(s2)):
                if s1[i]==s2[j]:
                    arr[i][j] = 1 + arr[i-1][j-1]
                else:
                    arr[i][j] = max(arr[i-1][j],arr[i][j-1])
                maxi = max(maxi,arr[i][j])
        return maxi
		```