Mô phỏng thuật toán Dãy con chung dài nhất

Longest Common Subsequence · Nhóm: Quy hoạch động

Dãy con chung dài nhất (Longest Common Subsequence), nhóm Quy hoạch động.

Mã Python

def lcs(s, p):
    n, m = len(s), len(p)
    dp = [[0]*(m+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, m+1):
            if s[i-1] == p[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    # backtrack from (n, m) to rebuild string
    return dp[n][m]

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.