Pythonで方程式を修正するために実行する修正の数を見つけるプログラム

x + y=zの形式の方程式を表す文字列sがあるとします。方程式が真になるように、sに追加する必要のある最小桁数を見つける必要があります。

したがって、入力がs ='2 + 6 =7'の場合、出力は2になります。

「1」と「2」を挿入することで、方程式を「21 + 6=27」に変えることができます。したがって、必要な修正の総数は2です。

これを解決するには、次の手順に従います-

• sを「+」文字に基づいて分割し、左側をAに、右側を残りに配置します

• 残りを「=」文字に基づいて部分に分割し、左側をBに、右側をCに配置します

• dp（Aのサイズ-1、Bのサイズ-1、Cのサイズ-1、0）

  を返します。

• 関数dp（）を定義します。これにはi、j、k、キャリーが必要です

• i<=-1かつj<=-1かつk<=-1の場合、

  • キャリーが0と同じ場合は0を返し、それ以外の場合は1を返します

• last1：=（A [i]）i>=0の場合は0

• last2：=（B [j]）if j>=0それ以外の場合0

• last3：=（C [k]）k>=0の場合は0

• prefix1：=（A[インデックス0からi+ 1]）i>=0の場合は0

• prefix2：=（B[インデックス0からj+ 1]）j>=0の場合は0

• prefix3：=（C[インデックス0からk+ 1]）k>=0の場合は0

• i<=-1およびj<=-1の場合、

  • rhs：=prefix3-キャリー

  • rhs <=0の場合、

    • 戻る|rhs|

  • iが-1と同じか、jが-1と同じ場合、

    • 文字列rhsの戻りサイズ

  • それ以外の場合

    • Falseを返す

  • k <=-1の場合、

    • str（prefix1 + prefix2 +キャリー）の戻りサイズ

  • ans：=無限大

  • キャリー2、lhs：=商を返し、余りを10で割る（キャリー+ last1 + last2）

  • lhsがlast3と同じ場合、

    • ans：=dp（i-1、j-1、k-1、carry2）

  • req：=last3-キャリー-last2

  • extra_zeros：=最大0、-1-i

  • キャリー2：=req<0の場合は1それ以外の場合は0

  • ans：=ansの最小値、1 + extra_zeros + dp（-1、i、j-1、k-1、carry2の最大値）

  • req：=last3-キャリー-last1

  • extra_zeros：=最大0、-1-j

  • キャリー2：=req<0の場合は1それ以外の場合は0

  • ans =最小（ans、1 + extra_zeros + dp（i-1、max（-1、j）、k-1、carry2））

  • キャリー2、lhs：=商を返し、余りを10で割る（last1 + last2 +キャリー）

  • ans：=ansの最小値、1 + dp（i-1、j-1、k、carry2）

  • ansを返す

• メインメソッドからreturndp（A – 1のサイズ、B – 1のサイズ、C – 1のサイズ）

例

理解を深めるために、次の実装を見てみましょう-

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