找出在Python中修复方程式所需的校正数的程序
假设我们有一个字符串s，它表示形式为x+y=z的方程式。我们必须找到需要加到s中的最小位数，以便等式变为真。
因此，如果输入类似于s='2+6=7'，则输出将为2。
我们可以通过插入“1”和“2”将等式变成“21+6=27”。因此，所需的更正总数为2。
在线示例
让我们看下面的实现以更好地理解-
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'))输入值
'2+6=7'输出结果
2