First List three key points of the dynamic programming problem-solving technique with a short description for each key point. Then take the Levenshtein edit distance code snippet below as an example to illustrate how three key points of the dynamic programming technique you listed above are applied in Levenshtein's solution. You may refer to the line number to explain your points. 1 def editDistanceDP(s1, s2, m, n, memo): 2 if memo[m][n] > -1: return memo[m][n] 3 if m == 0 : memo[m][n] = n; return memo[m][n] 4 if n == 0 : memo[m][n] = m; return memo[m][n] 5 if s1[m-1] == s2[n-1] : 6 memo[m][n] = editDistanceDP(s1, s2, m-1, n-1, memo) 7 return memo[m][n] 8 memo[m][n] = 1 + min(editDistanceDP(s1, s2, m, n-1, memo),\ 9 editDistanceDP(s1, s2, m-1, n, memo),\ 10 editDistanceDP(s1, s2, m-1, n-1,memo)) 11 return memo[m][n]
First List three key points of the dynamic
Then take the Levenshtein edit distance code snippet below as an example to illustrate how three key points of the dynamic programming technique you listed above are applied in Levenshtein's solution. You may refer to the line number to explain your points.
1 def editDistanceDP(s1, s2, m, n, memo):
2 if memo[m][n] > -1: return memo[m][n]
3 if m == 0 : memo[m][n] = n; return memo[m][n]
4 if n == 0 : memo[m][n] = m; return memo[m][n]
5 if s1[m-1] == s2[n-1] :
6 memo[m][n] = editDistanceDP(s1, s2, m-1, n-1, memo)
7 return memo[m][n]
8 memo[m][n] = 1 + min(editDistanceDP(s1, s2, m, n-1, memo),\
9 editDistanceDP(s1, s2, m-1, n, memo),\
10 editDistanceDP(s1, s2, m-1, n-1,memo))
11 return memo[m][n]
Step by step
Solved in 4 steps
