获得目标数的最少操作次数

Question

如果有字符串格式的数字列表，例如[“1”、“5”、“8”]，有效操作列表为“+”、“-”和“*”以及目标数字。找出构建目标数所需的最少操作数数。另外，您可以连接给定列表中的数字。示例：

 ex1:
   digits: ["1"]
   Target: 1
   min number of operations needed is 0 since 1 can be represented with 1

 ex2:
   digits: ["1"]
   Target: 11
   min number of operations needed is 0 since 11 can be represented with 1 (concatenate 1s)

 ex3:
   digits: ["1"]
   Target: 21
   min number of operations needed is 2 since:
      11 + 11 - 1 = 21 ==> two operations 

有什么想法吗？我不认为贪婪算法会起作用，因为我们必须探索整个可能性空间，这会导致回溯/递归/DP。使用“-”对我来说有点不直观，因为我们可以超出目标并使用“-”返回目标，而不是只是“+”和“*”。

Answer 1

您必须通过增加长度来探索所有可能的字符串，直到达到目标值。为了优化，您可以在新字符串在语法上无效时立即停止构建。还可以避免预先生成无效字符串（例如，运算符可能不会出现在最后位置）。

但我不认为有任何技巧可以避免指数搜索空间。