Old Top Coder谜语:通过插入+来制作一个数字

Question

我正在考虑这个topcoder问题.

给定一串数字,找到字符串所需的最小加法数等于某个目标数.每次添加相当于在数字串中的某处插入加号.插入所有加号后,像往常一样评估总和.

例如,考虑"303"和目标总和6.最佳策略是"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 的味道。