整数拆分使乘积最大(LC343)
哪些公司问过
答案要点
- 尽量拆成 3,余 1 时用 2+2 代替 3+1,余 2 时乘 2
- 大于 4 的因子再拆不会变差,所以只用 2 和 3
- 2 最多出现两次,因为 2×2×2 < 3×3
- 边界:n=2 返回 1,n=3 返回 2(至少拆成两部分)
- DP:dp[i] = max(j×(i−j), j×dp[i−j]),O(n²)
易错点
- n=2、n=3 时直接用贪心公式,得到错误结果
- 余 1 时直接乘 1,没有换成 2×2
- DP 只比较 j×dp[i−j],漏掉不继续拆分的情况
面试官常见追问
- DP 里为什么要同时比较 j×(i−j) 和 j×dp[i−j]?
- n 很大要取模时贪心还成立吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场