求基于可拼接数字与+-*运算构建目标数的最少操作次数算法

问题明确 #

给定字符串形式的数字列表（例如["1","5","8"]），允许使用+、-、*三种运算，同时可将列表中的数字拼接成更大的数，目标数范围为[0,99999]，需要找出构建目标数所需的最少运算操作次数（拼接不算运算操作）。

示例说明 #

示例1：
  digits: ["1"]
  Target: 1
  最少操作次数为0，直接用数字1即可表示目标数

示例2：
  digits: ["1"]
  Target: 11
  最少操作次数为0，通过拼接两个1得到11即可

示例3：
  digits: ["1"]
  Target: 21
  最少操作次数为2，因为：
     11 + 11 - 1 = 21 → 共两次运算操作

可行算法方案 #

贪心算法确实不适用——减法的存在意味着“先凑出远超目标的数再减回目标”可能比直接凑目标数操作更少，局部最优无法保证全局最优。推荐采用广度优先搜索（BFS）或带记忆化的动态规划方案，以下是具体思路：

1. 预先生成所有可拼接数字 #

首先从给定的数字列表出发，生成所有不超过99999的拼接数，记录每个拼接数对应的“数字使用量”（比如1用1个数字，11用2个数字），这些拼接数的运算操作次数初始为0（因为拼接不算运算）。

2. BFS 求最少操作次数 #

BFS是最优选择，因为它按操作次数从小到大遍历状态，一旦找到目标数，对应的次数就是最小值，可直接返回：

• 每个状态定义为(当前数值, 累计操作次数)，初始队列包含所有预生成的拼接数（操作次数为0）。
• 对队列中的每个状态，遍历所有预生成的拼接数，分别进行+、-、*运算，生成新的数值：
  • 若新数值在[-99999, 99999]范围内（允许中间负数，只要最终目标在合法区间），且未记录过更优的操作次数，则更新记录并将新状态加入队列。
• 维护一个字典min_ops，记录每个数值已找到的最少操作次数，避免重复处理更差的状态。

3. 动态规划方案（预处理所有可能值） #

定义dp[n]为得到数值n所需的最少操作次数：

• 初始化：所有预生成的拼接数n，dp[n] = 0。
• 迭代更新：遍历所有可能的数值对(i, j)，分别计算i+j、abs(i-j)、i*j的最少操作次数：
  • dp[i+j] = min(dp[i+j], dp[i] + dp[j] + 1)
  • dp[abs(i-j)] = min(dp[abs(i-j)], dp[i] + dp[j] + 1)
  • dp[i*j] = min(dp[i*j], dp[i] + dp[j] + 1)（注意i*j不能超过99999）
• 重复迭代直到没有dp值更新为止，之后可直接查询目标数对应的dp值。

核心注意点 #

• 减法允许中间结果为负数，但需限制范围避免状态爆炸；
• 记忆化剪枝是关键，无论BFS还是DP，都要避免重复处理同一数值的更差状态；
• 拼接数的生成要彻底，比如给定["1"]，要生成1、11、111…直到超过99999为止。

内容的提问来源于stack exchange，提问作者Alan