Advertisement
viligen

longest_common_subs_DP

Aug 10th, 2022
531
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.38 KB | None | 0 0
  1. first = input()
  2. second = input()
  3.  
  4. rows = len(first) + 1
  5. cols = len(second) + 1
  6.  
  7. dp = [[0] * cols for _ in range(rows)]
  8.  
  9. for row in range(1, rows):
  10.     for col in range(1, cols):
  11.         if first[row-1] == second[col -1]:
  12.             dp[row][col] = dp[row-1][col-1] + 1
  13.         else:
  14.             dp[row][col] = max(dp[row-1][col], dp[row][col-1])
  15.  
  16. print(dp[rows-1][cols-1])
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement