algorithm - 旧顶级编码器谜语 : Making a number by inserting +

Question

我在想this topcoder problem .

Given a string of digits, find the minimum number of additions required for the string to equal some target number. Each addition is the equivalent of inserting a plus sign somewhere into the string of digits. After all plus signs are inserted, evaluate the sum as usual.

For example, consider "303" and a target sum of 6. The best strategy is "3+03".

我会用暴力解决它，如下所示:

for each i in 0 to 9 // i -- number of plus signs to insert
  for each combination c of i from 10
    for each pos in c // we can just split the string w/o inserting plus signs
      insert plus sign in position pos 
    evaluate the expression
    if the expression value == given sum
      return i

有意义吗？从性能的角度来看，它是最优的吗？

...

好吧，现在我看到动态规划解决方案会更有效率。然而，如果所提出的解决方案无论如何都有意义，那就很有趣了。

Answer 1

这当然不是最佳选择。例如，如果给定字符串“1234567890”并且目标是一个三位数，您知道必须将字符串至少拆分为四个部分，因此您无需检查 0、1 或 2 插入.此外，目标限制了允许插入位置的范围。这两点对短字符串的影响很小，但对较长的字符串影响很大。但是，我怀疑有更好的方法，有点 DP 的味道。