旧的 Top Coder 谜语：通过插入 + 来生成数字

我正在考虑.

给定一串数字，找到该字符串等于某个目标数字所需的最少加法次数。每次添加都相当于在数字字符串中的某处插入一个加号。插入所有加号后，照常计算总和。

例如，考虑“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

是否有意义？从性能的角度来看它是否是最佳的？

...

好吧，现在我发现动态编程解决方案会更有效。然而，如果所提出的解决方案有意义的话，那就很有趣了。

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