#030Memoization Key Collision in DP
dsa.medDSA
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]
no lines flagged
#030PracticeMedium20 min · 120 XP
Memoization Key Collision in DP
A memoized longest common subsequence function returns wrong answers for some inputs because the cache key is ambiguous.
Flagged lines
No lines flagged yet
What's wrong?
Flag a line or write a note to submit.