1def lcs(s1, s2, i, j, memo={}):
2 if i == 0 or j == 0:
3 return 0
4 key = (i, j)
5 if key in memo:
6 return memo[key]
7 if s1[i-1] == s2[j-1]:
8 memo[key] = 1 + lcs(s1, s2, i-1, j-1, memo)
9 else:
10 memo[key] = max(lcs(s1, s2, i-1, j, memo),
11 lcs(s1, s2, i, j-1, memo))
12 return memo[key]