โปรแกรมหาจำนวนการแก้ไขน้อยที่สุดเพื่อทำให้สมการถูกต้องใน Python

คำอธิบายโจทย์

ให้สตริงสมการ x+y=z หาจำนวนตัวเลขน้อยที่สุดที่ต้องแทรก (insert) เข้าไปใน s เพื่อให้สมการเป็นจริง

ตัวอย่าง

s = '2+6=7' → 2 (แทรก 1, 2 ได้ "21+6=27")

วิธีแก้ปัญหา

DP บนตัวเลข (Digit DP) จากหลักหน่วยขึ้นไป:

1. แยก A, B, C จากสตริง
2. dp(i, j, k, carry) = insert น้อยที่สุดสำหรับ suffix A[i:], B[j:], C[k:] พร้อม carry
3. Base case: หมดตัวเลขทั้ง 3 → 0 ถ้า carry=0 ไม่อย่างนั้น 1
4. ลองทุกกรณี: match ทั้ง 3, insert ใน A, insert ใน B, insert ใน C
5. ใช้ divmod จัดการ carry

โค้ด Python

class Solution:
    def solve(self, s):
        A, rest = s.split("+")
        B, C = rest.split("=")
        
        from functools import lru_cache
        
        @lru_cache(None)
        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'))

อินพุต

'2+6=7'

เอาต์พุต

2