LeetCode 650. 两个键的键盘
目录
题目描述
题意分析
要什么：记事本上初始有 1 个字符
A，每次操作只能二选一：把当前全部内容复制到剪贴板，或者把剪贴板内容粘贴到末尾。问最少多少次操作能得到恰好n个A。
约束透露的信号：复制的对象是「全部内容」而不是任意片段，这个「全部」是全题的关键——它意味着剪贴板里的数量只能是某个历史时刻的总量，而粘贴只是把这个量一份份加回去。于是「复制一次 + 粘贴t次」把总量从x变成x·(t+1)，代价t+1次操作。整个过程因此是一串乘法，而不是任意的加法组合。n只到 1000 说明 $O(n^2)$ 的 DP 也能过，但既然结构是乘法，就该往因数分解上想。
边界：n = 1时初始状态已经满足，答案是 0，一次操作都不需要；n为质数时无法拆分，只能一次复制加n-1次粘贴，答案就是n；粘贴不能凭空发生，第一次操作必须是复制。
解法：质因数分解求和
核心思路
先建立最朴素的模型：设
f[i]为得到i个字符的最少操作数，若j是i的因子，则可以先花f[j]步得到j个字符，再用「一次复制 +i/j - 1次粘贴」共i/j步把它翻到i，于是f[i] = min(f[j] + i/j)。枚举所有因子对，时间约 $O(n\sqrt n)$。这个 DP 是对的，但它掩盖了结构。
观察这个转移会发现：任何一次「复制 + 若干粘贴」都把当前数量乘以一个整数p，代价恰好也是p。所以整个过程等价于把n写成若干整数的乘积 $n = p_1 p_2 \cdots p_m$，总代价是 $p_1 + p_2 + \cdots + p_m$。问题从「最少操作数」变成了纯数学的「把n分解成整数乘积，使因子之和最小」。
接下来只需一条不等式：若某个因子p是合数，写成p = a·b（a, b ≥ 2），则把它拆开更划算，因为 $a + b \le a\cdot b$ 对 $a, b \ge 2$ 恒成立（移项即 $(a-1)(b-1) \ge 1$），且仅当a = b = 2时取等。所以最优分解里不存在合数因子，每个因子都必须是质数。
由此得到结论与要维护的量：答案等于n的全部质因子之和（重复的质因子按重数重复计入）。算法只剩下一件事——做质因数分解，一边分解一边把因子累加进answer。
解题步骤
- 令
answer = 0，从d = 2开始试除，循环条件是d * d <= n。为什么上界是 $\sqrt n$：一个合数必有一个不超过其平方根的质因子，所以试除到 $\sqrt n$ 之后若n还大于 1，剩下的n本身必是质数。注意这里的n是被不断除小的当前值，上界随之动态收缩，效率远好于固定上界。- 内层用
while (n % d == 0)反复除，每除一次就answer += d。为什么用 while 而不是 if：质因子可能出现多次（如8 = 2×2×2），每一重都对应一次独立的「乘以 2」操作，都要计入代价；写成if只会算一次。- 为什么试除时不用先判断
d是不是质数：因为比d小的所有质因子已经在之前的轮次里被除干净了，轮到d时若n % d == 0，d必然不含更小的质因子，也就必然是质数。这是试除法自带的性质，省掉了筛素数的步骤。- 循环结束后若
n > 1，执行answer += n。为什么必须补这一步：剩下的n是一个大于 $\sqrt{原值}$ 的质因子（如n = 14除掉 2 后剩 7），试除循环够不着它。漏掉这句会让所有含大质因子的输入全部算错。- 返回
answer。为什么n = 1时自动正确：d = 2时4 <= 1不成立，循环体一次都不执行；随后1 > 1为假，直接返回 0，恰好对应「初始就有 1 个 A，无需操作」。- 以
n = 12走一遍。answer = 0。d = 2：4 <= 12进入循环，12 % 2 == 0故answer = 2、n = 6；6 % 2 == 0故answer = 4、n = 3；3 % 2 != 0退出内层。回到外层判断d = 2时4 <= 3已不成立，循环结束。此时n = 3 > 1，补上answer = 7。返回 7。对照实际操作序列验证：从 1 个 A 出发，复制 + 粘贴 1 次得到 2 个（2 步），复制 + 粘贴 1 次得到 4 个（再 2 步），复制 + 粘贴 2 次得到 12 个（再 3 步），共2 + 2 + 3 = 7步，与12 = 2 × 2 × 3的质因子之和完全吻合。
代码实现
// 核心实现：质因数分解求和，维护必要状态并避免重复处理。
class Solution {
public int minSteps(int n) {
int answer = 0;
for (int d = 2; d * d <= n; d++) {
while (n % d == 0) {
answer += d;
n /= d;
}
}
if (n > 1) {
answer += n;
}
return answer;
}
}
// 核心实现：质因数分解求和，维护必要状态并避免重复处理。
func minSteps(n int) int {
answer := 0
for d := 2; d*d <= n; d++ {
for n%d == 0 {
answer += d
n /= d
}
}
if n > 1 {
answer += n
}
return answer
}
复杂度分析
- 时间复杂度：$O(\sqrt n)$。凭什么：外层
d最多枚举到 $\sqrt n$；内层的除法总次数不超过n的质因子个数，而这个数不超过 $\log_2 n$，被外层的 $\sqrt n$ 吸收。- 空间复杂度：$O(1)$。凭什么：只用了
answer和d两个标量，既没有 DP 数组也没有存放因子的容器。
关键点总结
- 先识别操作的代数结构：本题「复制全部 + 粘贴」把加法伪装成了乘法，一旦看出「一段操作 = 乘以 p，代价 p」，问题立刻从搜索/DP 塌缩成数论。读题时多问一句「这个操作在数值上到底做了什么」往往能省掉一整个 DP 表。
- 合数因子必可拆：$a + b \le ab$（$a,b\ge 2$）是把「任意整数分解」收紧到「质数分解」的唯一依据。这条不等式在整数拆分、乘积最大化一族题里反复出现，值得记住并能当场证明。
- 试除法的两个惯用细节：上界用不断更新的
d * d <= n而非固定值，循环后补上「剩余的n若大于 1 则它是质数」。这两点缺一不可，后者是最常见的漏写点。- 面试视角：稳妥的答法是先给 DP 再给数学——先写出
f[i] = min(f[j] + i/j)（j | i）说明思路完备，再指出它的最优解恰好是质因子之和从而优化到 $O(\sqrt n)$，并现场证明「合数因子可拆」。只给数学结论而证明不出来，容易被认为是背题。n = 1这类「初始状态已达标」的边界要单独在脑子里跑一遍。本题的写法恰好天然正确，但如果改成先无条件做一次复制就会错。
易错点总结
- 错误写法：漏掉循环结束后的
if (n > 1) answer += n；用例n = 7→ 外层d = 2时4 <= 7成立但 7 不被 2 整除，d = 3时9 <= 7不成立退出，返回 0，正确答案是 7。- 错误写法：内层用
if (n % d == 0)而不是while；用例n = 8→ 只除一次得到answer = 2、n = 4，随后d = 2的循环已推进到d = 3，最终返回2 + 4 = 6，正确答案是 6……在这一例上侥幸相等，但换成n = 16会得到2 + 8 = 10，而正确答案是 8。- 错误写法：外层循环条件写成
d <= n或d <= sqrt(原始 n)；用例n = 1000000007级别的大质数（若放宽数据范围）→ 前者退化成 $O(n)$ 严重超时，后者在n被除小后仍按原始上界空转，浪费大量无效试除。- 错误写法：把答案理解成「质因子个数」而不是「质因子之和」；用例
n = 9→ 返回 2，正确答案是3 + 3 = 6。- 错误写法：把代价算成
i/j - 1（只数粘贴次数，忘了复制那一次）；用例n = 3→ 得到 2，正确答案 3，每一段乘法都少算一次复制操作。- 错误写法：认为「乘以更大的数更省」于是贪心地每次取最大因子；用例
n = 12→ 若先乘 12（代价 12）直接返回 12，正确答案 7；最优是拆成尽可能小的质因子。- 错误写法：特判
n = 1时返回 1；用例n = 1→ 返回 1，正确答案是 0，初始就已经有一个 A。- 错误写法：从
d = 1开始试除；用例 任意n > 1→n % 1 == 0恒成立且n / 1不变，内层 while 死循环。- 错误写法：DP 版本里把
f[i] = min(f[j] + i/j)写成f[i] = min(f[j] + j)；用例n = 6→ 因子j = 2时算成f[2] + 2 = 4，而正确应为f[2] + 3 = 5；两个方向的代价被张冠李戴，答案偏小。- 错误写法：DP 版本枚举因子时只枚举到
i / 2却忘记j必须整除i；用例n = 6→ 把j = 4之类的非因子也纳入转移，得到不可达的状态组合，答案偏小且无法对应任何真实操作序列。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 343. 整数拆分 | 中等 | 同样靠不等式把任意拆分收紧到固定形态，但目标是最大化乘积而非最小化和 |
| 279. 完全平方数 | 中等 | 分解对象换成平方数之和，不存在质因数式的结构，只能 DP 或用四平方定理 |
| 322. 零钱兑换 | 中等 | 可用面额任意给定、不再有整除关系，贪心失效，必须完整跑完全背包 |