面试题库 › C++ / 后端 › 整数拆分使乘积最大(LC343)

整数拆分使乘积最大(LC343)

难度 ★★☆在 1 场真实面经中被问到 方向:C++ / 后端考点:动态规划

哪些公司问过

3601

常见岗位:C/C++ 软件开发

答案要点

  1. 尽量拆成 3,余 1 时用 2+2 代替 3+1,余 2 时乘 2
  2. 大于 4 的因子再拆不会变差,所以只用 2 和 3
  3. 2 最多出现两次,因为 2×2×2 < 3×3
  4. 边界:n=2 返回 1,n=3 返回 2(至少拆成两部分)
  5. DP:dp[i] = max(j×(i−j), j×dp[i−j]),O(n²)

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题