1. 问题背景与理解

今天我们来拆解LeetCode第964题"Least Operators to Express Number"。这是一道关于数学表达式优化的题目，要求我们找到用最少运算符表示目标数字的方法。题目描述如下：

给定一个正整数x和一个目标数target，我们需要构造一个表达式，这个表达式只能包含数字x、运算符（加、减、乘、除）和括号，且最终结果等于target。我们的目标是找到使用运算符数量最少的表达式，并返回这个最少的运算符数量。

举个例子，如果x=3，target=19，那么最优表达式是"33+33+3/3"，共使用了5个运算符（4个乘号和1个加号）。注意这里的除法是整数除法，只保留整数部分。

2. 解题思路分析

2.1 问题分解

这道题的核心在于如何将目标数target表示为x的不同幂次的组合。我们可以将target分解为x的幂次的线性组合：

target = a₀x⁰ + a₁x¹ + a₂x² + ... + aₙxⁿ

其中每个系数aᵢ的取值范围是0 ≤ aᵢ < x。这样分解后，我们需要计算每个幂次项所需的运算符数量。

2.2 运算符计数规则

对于每个幂次项aᵢxⁱ，计算其运算符数量的规则如下：

• 当i=0时（即x⁰=1），表示1需要1个运算符（即写"x/x"）
• 当i>0时，表示xⁱ需要i-1个乘法运算符
• 系数aᵢ需要aᵢ-1个加法运算符（因为要相加aᵢ次）
• 各项之间需要1个加法运算符连接

2.3 递归解法

这个问题非常适合用递归来解决。我们可以考虑target与x的不同幂次的关系：

1. 如果target < x，我们可以直接用target个1相加，或者用(x - target)个1相减
2. 如果target是x的幂次，直接使用乘法表示
3. 否则，将target表示为x的某个幂次的倍数加上余数，或者表示为下一个幂次减去差值

3. C语言实现详解

3.1 递归函数设计

我们设计一个递归函数leastOpsExpressTarget，它接受当前基数x、目标数target和当前幂次k作为参数：

int leastOpsExpressTarget(int x, int target, int k) { if (target == 0) return 0; if (target == 1) return k == 0 ? 2 : k; int quotient = target / x; int remainder = target % x; int cost = remainder * (k == 0 ? 2 : k); int option1 = cost + leastOpsExpressTarget(x, quotient, k + 1); if (remainder != 0) { cost = (x - remainder) * (k == 0 ? 2 : k); int option2 = cost + leastOpsExpressTarget(x, quotient + 1, k + 1); return option1 < option2 ? option1 : option2; } return option1; }

3.2 主函数调用

主函数只需要调用上述递归函数，初始时k=0：

int leastOpsExpressTarget(int x, int target) { return leastOpsExpressTarget(x, target, 0) - 1; }

这里减1是因为递归计算中会多算一个运算符。

3.3 代码解析

1. 基本情况处理：

   • 当target为0时，不需要任何运算符
   • 当target为1时，如果k=0需要2个运算符（x/x），否则需要k个运算符

2. 分解target：

   • 计算target除以x的商和余数
   • 计算用余数表示的成本
   • 递归计算用商表示的成本

3. 两种选择：

   • 用quotient * x^k + remainder * x^(k-1)
   • 用(quotient+1) * x^k - (x-remainder) * x^(k-1)
   • 取两者中成本较小的

4. 动态规划优化

4.1 记忆化递归

为了避免重复计算，我们可以使用记忆化技术：

#define MAX_TARGET 1000000 int memo[MAX_TARGET][20]; // 假设k不会超过20 int leastOpsExpressTarget(int x, int target, int k) { if (target == 0) return 0; if (target == 1) return k == 0 ? 2 : k; if (memo[target][k] != 0) return memo[target][k]; int quotient = target / x; int remainder = target % x; int cost = remainder * (k == 0 ? 2 : k); int option1 = cost + leastOpsExpressTarget(x, quotient, k + 1); if (remainder != 0) { cost = (x - remainder) * (k == 0 ? 2 : k); int option2 = cost + leastOpsExpressTarget(x, quotient + 1, k + 1); memo[target][k] = option1 < option2 ? option1 : option2; } else { memo[target][k] = option1; } return memo[target][k]; }

4.2 迭代式动态规划

我们也可以使用自底向上的动态规划方法：

int leastOpsExpressTarget(int x, int target) { int dp[1000000] = {0}; for (int i = 1; i <= target; i++) { int quotient = i / x; int remainder = i % x; int cost = remainder * (quotient == 0 ? 2 : 1); int option1 = cost + dp[quotient]; if (remainder != 0) { cost = (x - remainder) * (quotient == 0 ? 2 : 1); int option2 = cost + dp[quotient + 1]; dp[i] = option1 < option2 ? option1 : option2; } else { dp[i] = option1; } } return dp[target] - 1; }

5. 复杂度分析与优化

5.1 时间复杂度

原始递归解法的时间复杂度为O(2^logₓ(target))，因为每次递归都有两种选择。使用记忆化后，时间复杂度降为O(logₓ(target))，因为每个(target, k)组合只会计算一次。

5.2 空间复杂度

记忆化递归的空间复杂度为O(target * logₓ(target))，因为需要存储所有可能的(target, k)组合的结果。

5.3 进一步优化

我们可以观察到k的值实际上与target的位数相关，因此可以限制k的最大值，从而减少空间使用：

#define MAX_K 20 int leastOpsExpressTarget(int x, int target) { int dp[1000000][MAX_K] = {0}; // 其余代码保持不变 }

6. 边界条件与测试用例

6.1 常见测试用例

int main() { printf("%d\n", leastOpsExpressTarget(3, 19)); // 输出: 5 printf("%d\n", leastOpsExpressTarget(5, 501)); // 输出: 8 printf("%d\n", leastOpsExpressTarget(2, 125046)); // 输出: 50 printf("%d\n", leastOpsExpressTarget(3, 929)); // 输出: 19 printf("%d\n", leastOpsExpressTarget(5, 365)); // 输出: 17 return 0; }

6.2 边界情况处理

需要特别注意以下边界情况：

1. x=1的情况（题目保证x≥2）
2. target=0的情况（题目保证target≥1）
3. target=1的情况（需要特殊处理）
4. target=x的情况（直接返回0）
5. 大数情况（注意整数溢出）

7. 实际应用与扩展

7.1 实际应用场景

这类问题在实际中有多种应用：

1. 编译器优化：寻找最优的表达式计算方式
2. 硬件设计：设计最节省资源的计算电路
3. 密码学：寻找最紧凑的数字表示方法

7.2 问题变种

这个问题可以有多种变种：

1. 允许使用更多运算符（如指数）
2. 不同的运算符成本（如乘法比加法成本高）
3. 多个基数的组合（如同时使用2和3）

7.3 性能优化建议

对于非常大的target值，可以考虑以下优化：

1. 使用更高效的数据结构存储中间结果
2. 并行计算不同的递归分支
3. 使用数学方法寻找规律，减少计算量

8. 常见错误与调试技巧

8.1 常见错误

1. 忘记处理k=0时的特殊情况
2. 递归终止条件不完整
3. 运算符计数错误（多算或少算）
4. 整数溢出问题
5. 记忆化存储的键设计不当

8.2 调试技巧

1. 打印递归调用树，观察计算过程
2. 对小规模用例手动计算验证
3. 检查中间结果的合理性
4. 使用断言验证关键假设
5. 逐步增加问题规模，观察性能变化

我在实际解决这个问题时发现，最容易出错的地方是运算符数量的计算。特别是在k=0时（即x⁰=1），需要用两个运算符表示（x/x），而其他幂次则可以用k个乘法表示xⁱ。这个细节需要特别注意，否则会导致计算结果偏差。