LeetCode 964题解析：最少运算符表达数字的数学优化

1. 问题背景与理解今天我们来拆解LeetCode第964题Least Operators to Express Number。这是一道关于数学表达式优化的题目要求我们找到用最少运算符表示目标数字的方法。题目描述如下给定一个正整数x和一个目标数target我们需要构造一个表达式这个表达式只能包含数字x、运算符加、减、乘、除和括号且最终结果等于target。我们的目标是找到使用运算符数量最少的表达式并返回这个最少的运算符数量。举个例子如果x3target19那么最优表达式是33333/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ⁱ计算其运算符数量的规则如下当i0时即x⁰1表示1需要1个运算符即写x/x当i0时表示xⁱ需要i-1个乘法运算符系数aᵢ需要aᵢ-1个加法运算符因为要相加aᵢ次各项之间需要1个加法运算符连接2.3 递归解法这个问题非常适合用递归来解决。我们可以考虑target与x的不同幂次的关系如果target x我们可以直接用target个1相加或者用(x - target)个1相减如果target是x的幂次直接使用乘法表示否则将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 主函数调用主函数只需要调用上述递归函数初始时k0int leastOpsExpressTarget(int x, int target) { return leastOpsExpressTarget(x, target, 0) - 1; }这里减1是因为递归计算中会多算一个运算符。3.3 代码解析基本情况处理当target为0时不需要任何运算符当target为1时如果k0需要2个运算符x/x否则需要k个运算符分解target计算target除以x的商和余数计算用余数表示的成本递归计算用商表示的成本两种选择用quotient * x^k remainder * x^(k-1)用(quotient1) * 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 边界情况处理需要特别注意以下边界情况x1的情况题目保证x≥2target0的情况题目保证target≥1target1的情况需要特殊处理targetx的情况直接返回0大数情况注意整数溢出7. 实际应用与扩展7.1 实际应用场景这类问题在实际中有多种应用编译器优化寻找最优的表达式计算方式硬件设计设计最节省资源的计算电路密码学寻找最紧凑的数字表示方法7.2 问题变种这个问题可以有多种变种允许使用更多运算符如指数不同的运算符成本如乘法比加法成本高多个基数的组合如同时使用2和37.3 性能优化建议对于非常大的target值可以考虑以下优化使用更高效的数据结构存储中间结果并行计算不同的递归分支使用数学方法寻找规律减少计算量8. 常见错误与调试技巧8.1 常见错误忘记处理k0时的特殊情况递归终止条件不完整运算符计数错误多算或少算整数溢出问题记忆化存储的键设计不当8.2 调试技巧打印递归调用树观察计算过程对小规模用例手动计算验证检查中间结果的合理性使用断言验证关键假设逐步增加问题规模观察性能变化我在实际解决这个问题时发现最容易出错的地方是运算符数量的计算。特别是在k0时即x⁰1需要用两个运算符表示x/x而其他幂次则可以用k个乘法表示xⁱ。这个细节需要特别注意否则会导致计算结果偏差。