c++ - 使方程 (x = y) 正确所需的最小加号

Question

Problem Statement:

Given an equation “x=y”, for example, “111=12”, you need to add plusesinside x to make the equation correct. In our example “111=12”, we canadd one plus “11+1=12” and the equation becomes correct. You need tofind the minimum number of pluses to add to x to make the equationcorrect. If there is no answer print -1.

Note that the value of y won’t exceed 5000. The numbers in thecorrected equation may contain arbitrary amounts of leading zeros.

Input Format The first line contains a string, A as described in theproblem statement.

Constraints 1 <= len(A) <= 10^3

我尝试了递归方法。对于“x”中的每个字符，我有两个选项可以在当前数字旁边包含加号或移动到下一个数字(通过将当前数字包含在下一个数字中)我检查了所有组合并找到最小的优点。如您所知，这在复杂性上呈指数级增长。我无法对这个问题应用动态规划，因为我想不出动态规划的状态。
我知道这个问题可以通过动态规划解决。但是，我不知道 如何识别状态和转换 .

Answer 1

首先想到的是有一张 table

int f[N+1][M+1];

哪里 N = len(x)和 M = y .然后 f[i][j]将记录子问题的解 substr(x,0,i)=j ;即需要多少加号才能得到总和 j从第一 i x的位数.该表可以通过递归关系增量更新:

f[i][j] = minimum over 0 <= k < i of (f[k][j - atoi(substr(x,k,i))] + 1)

不可获得或越界的配置应理解为具有 f[i][j] == +infinity而不是 -1 .
表的大小为 O(N*M)，运行时间为 O(N² M)。
我会留下实现细节和启动条件供您完成。