Chương trình tìm tổng chữ số xóa nhỏ nhất để hai chuỗi số giống nhau trong Python

Cho 2 chuỗi số s, t. Xóa các chữ số để 2 chuỗi giống nhau, tối thiểu tổng các chữ số bị xóa.

Ví dụ: s="41272", t="172" → xóa '4' và '2' từ s → tổng = 6.

Giải thuật (LCS biến thể - Tích lũy giá trị chữ số chung lớn nhất)

Biến đổi bài toán: Thay vì tìm LCS theo độ dài, tìm dãy con chung có tổng giá trị chữ số * 2 lớn nhất (vì giữ lại chữ số = tiết kiệm 2 lần giá trị nó).

• table[i][j] = tổng giá trị * 2 lớn nhất của dãy con chung của s[:i] và t[:j].
• Nếu s[i-1] == t[j-1]: table[i][j] = table[i-1][j-1] + 2 * int(s[i-1]).
• Khác: max(table[i-1][j], table[i][j-1]).
• Kết quả = tổng tất cả chữ số - table[m][n].

Ví dụ minh họa

class Solution:
    def lcs(self, a, b, m, n):
        table = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if a[i - 1] == b[j - 1]:
                    table[i][j] = table[i - 1][j - 1] + 2 * (ord(a[i - 1]) - 48)
                else:
                    table[i][j] = max(table[i - 1][j], table[i][j - 1])
        return table[m][n]
    
    def solve(self, a, b):
        m, n = len(a), len(b)
        total = sum(ord(ch) - 48 for ch in a) + sum(ord(ch) - 48 for ch in b)
        return total - self.lcs(a, b, m, n)

ob = Solution()
s = "41272"
t = "172"
print(ob.solve(s, t))  # Output: 6

Đầu vào / Đầu ra

Input: "41272", "172"

Output: 6