https://leetcode.com/problems/longest-common-subsequence/
2d grid を作る。 row, col にそれぞれ、1行、1列追加して 0 を入れる。
grid の右下からループし、 縦横が同じ文字でマッチしたら、斜め左上に進む。 その際に1を足す。
マッチしなかったら、右横か下のどちらか大きい数字を入れる。
ループが終わりgrid[0][0] の箇所に 1番長い subsequence の数が入る。
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
dp = [[0 for j in range(len(text2) + 1)] for i in range(len(text1) + 1)]
for i in range(len(text1) - 1, -1, -1):
for j in range(len(text2) - 1, -1, -1):
if text1[i] == text2[j]:
dp[i][j] = 1 + dp[i + 1][j + 1]
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j + 1])
return dp[0][0]