algorithm - 在数字之间加上符号，使数字的结果为 100

Question

我需要以下问题的帮助。给定一个数字，我必须在数字之间放置符号(+、-、*、/)以检查是否有任何组合结果为 100。我们可以将数字分组为多于一个，但我们不能改变数字的顺序。例如 593347 → 5 + ((9/(3/34)) – 7) = 100,271353→2-(7*(((1/3)-5 )*3)=100，而 707409 永远不会得到 100。我可以理解动态规划是解决方案，但是我找不到确切的算法。提前致谢。

Answer 1

让我们简化一下。想象一下这个数字是 1234。

第 0 步:数字是 100 吗？没有

第 1 步:查看 1 和 234。

• 第 1a 步:我们能找到 1 + f(234) 的答案吗？这就要求我们用数字 234 调用我们的函数，然后回答 99(因为 1 + n =100 表示 n = 99)。
• 第 1b 步:1 - f(234) 怎么样？这需要我们用数字 234 调用我们的函数，并回答 -99(因为1 - n = 100 表示 n = -99)。
• 第 1c 步:1 * f(234) 怎么样？等

第 2 步:查看 12 和 34。

• 第 2a 步:我们能否找到 f(12) + f(34) 的答案？
• 第 2b 步:我们能否找到 f(12) - f(34) 的答案？
• 等等

每次使用特定数字和预期结果调用函数时，存储答案，以便在使用相同参数调用时可以再次使用它。

这是这个问题的动态规划解决方案的草图。

我怀疑这样做需要大量的计算时间和内存。当问题仅限于 + 和 - 时，这已经够难的了。参见 https://vortexwolf.wordpress.com/2013/12/07/algorithm-plus-minus-result-100/例如。