Chương trình tìm số chữ số cần chèn để sửa phương trình trong Python

Cho chuỗi s dạng "x+y=z". Tìm số chữ số tối thiểu cần chèn vào s để phương trình thành thật.

Ví dụ: s = '2+6=7' → 2 (chèn '1' và '2' thành "21+6=27").

Giải pháp

DP trên 3 chuỗi số A, B, C (tách bằng '+' và '='):

• dp(i, j, k, carry): số chữ số chèn tối thiểu cho hậu tố A[i:], B[j:], C[k:] với carry
• Base case: i,j,k < 0 → 0 nếu carry=0 else 1
• Xét các trường hợp: khớp chữ số, chèn vào A, chèn vào B, chèn vào C
• Dùng prefix để xử lý trường hợp một chuỗi đã hết

Ví dụ minh họa

class Solution:
    def solve(self, s):
        A, rest = s.split("+")
        B, C = rest.split("=")
        def dp(i, j, k, carry):
            if i <= -1 and j <= -1 and k <= -1:
                return 0 if carry == 0 else 1
            last1 = int(A[i]) if i >= 0 else 0
            last2 = int(B[j]) if j >= 0 else 0
            last3 = int(C[k]) if k >= 0 else 0
            prefix1 = int(A[:i+1]) if i >= 0 else 0
            prefix2 = int(B[:j+1]) if j >= 0 else 0
            prefix3 = int(C[:k+1]) if k >= 0 else 0
            if i <= -1 and j <= -1:
                rhs = prefix3 - carry
                if rhs <= 0:
                    return abs(rhs)
                if i == -1 or j == -1:
                    return len(str(rhs))
                else:
                    assert False
            if k <= -1:
                return len(str(prefix1 + prefix2 + carry))
            ans = float("inf")
            carry2, lhs = divmod(carry + last1 + last2, 10)
            if lhs == last3:
                ans = dp(i - 1, j - 1, k - 1, carry2)
            req = last3 - carry - last2
            extra_zeros = max(0, -1 - i)
            carry2 = 1 if req < 0 else 0
            ans = min(ans, 1 + extra_zeros + dp(max(-1, i), j - 1, k - 1, carry2))
            req = last3 - carry - last1
            extra_zeros = max(0, -1 - j)
            carry2 = 1 if req < 0 else 0
            ans = min(ans, 1 + extra_zeros + dp(i - 1, max(-1, j), k - 1, carry2))
            carry2, lhs = divmod(last1 + last2 + carry, 10)
            ans = min(ans, 1 + dp(i - 1, j - 1, k, carry2))
            return ans
        return dp(len(A) - 1, len(B) - 1, len(C) - 1, 0)

ob = Solution()
print(ob.solve('2+6=7'))

Đầu vào

'2+6=7'

Đầu ra

2