650. 两个键的键盘
题目描述
记事本里一开始只有一个字符 'A'。每一步可以做以下两种操作之一。
Copy All：把记事本当前的全部内容复制到剪贴板，不能只复制一部分。Paste：把剪贴板里上一次复制的内容追加到记事本末尾。
输入整数 n，返回让记事本里恰好出现 n 个 'A' 所需的最少操作次数。
输入：n = 3 输出：3
解释：先复制一次，再粘贴两次，共 3 步得到 "AAA"。
输入：n = 1 输出：0
解释：一开始就有 1 个 'A'，不需要操作。
数据范围
1 <= n <= 1000
解题思路：动态规划（按最小因子转移）
想得到 i 个 A，最后一次复制时屏上有 d 个（d 必须整除 i），然后复制 1 次、粘贴 i/d - 1 次，共 i/d 步，故 dp[i] = min(dp[d] + i/d)。可以证明，取 d = i / p（p 为 i 的最小质因子）即最优，所以只需从 2 开始找第一个因子 j：dp[i] = dp[i / j] + j；找不到（i 是质数）就是 dp[i] = i，即复制一次、粘贴 i - 1 次。最终 dp[n] 等于 n 的质因子之和。
为什么正确
计算 dp[i] 时，所有小于 i 的 dp 都已算好。对于 a, b >= 2 总有 a + b <= a · b，所以拆成质因子不会更差。
复杂度分析
时间 O(n√n)，空间 O(n)。
易错点
n = 1 时答案是 0，不需要任何操作。不能只复制一部分字符，所以最后一次复制时的数量必须整除 n。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def minSteps(self, n: int) -> int:
dp = [0] * (n + 1)
for i in range(2, n + 1):
dp[i] = i
for j in range(2, int(i ** 0.5) + 1):
if i % j == 0:
dp[i] = dp[i // j] + j
break
return dp[n]class Solution {
public int minSteps(int n) {
int[] dp = new int[n + 1];
for (int i = 2; i <= n; i++) {
dp[i] = i;
for (int j = 2; j * j <= i; j++) {
if (i % j == 0) {
dp[i] = dp[i / j] + j;
break;
}
}
}
return dp[n];
}
}class Solution {
public:
int minSteps(int n) {
vector<int> dp(n + 1, 0);
for (int i = 2; i <= n; i++) {
dp[i] = i;
for (int j = 2; j * j <= i; j++) {
if (i % j == 0) {
dp[i] = dp[i / j] + j;
break;
}
}
}
return dp[n];
}
};func minSteps(n int) int {
dp := make([]int, n+1)
for i := 2; i <= n; i++ {
dp[i] = i
for j := 2; j*j <= i; j++ {
if i%j == 0 {
dp[i] = dp[i/j] + j
break
}
}
}
return dp[n]
}var minSteps = function(n) {
const dp = new Array(n + 1).fill(0);
for (let i = 2; i <= n; i++) {
dp[i] = i;
for (let j = 2; j * j <= i; j++) {
if (i % j === 0) {
dp[i] = dp[i / j] + j;
break;
}
}
}
return dp[n];
};function minSteps(n: number): number {
const dp = new Array(n + 1).fill(0);
for (let i = 2; i <= n; i++) {
dp[i] = i;
for (let j = 2; j * j <= i; j++) {
if (i % j === 0) {
dp[i] = dp[i / j] + j;
break;
}
}
}
return dp[n];
}其他解法
动态规划逐个长度求最少操作数，完全机械；分解质因数先用数学证明答案是质因数之和，再直接计算，更快也更省空间。
解法 2：分解质因数 时间 O(√n)，空间 O(1)
一次“复制全部 + 粘贴 p − 1 次”用 p 步把长度乘以 p。得到 n 就是把 n 分解成若干个因子之积，总步数是这些因子之和。当 a, b ≥ 2 时 a + b ≤ a·b，合数因子拆开不会变差，所以答案就是 n 的质因数之和（计重数）。用试除法从 2 开始分解即可。
只需试除到 √n，空间常数。缺点是要先证明“拆成质因数最优”这一结论。
class Solution:
def minSteps(self, n: int) -> int:
ans = 0
p = 2
while p * p <= n:
while n % p == 0:
ans += p
n //= p
p += 1
if n > 1:
ans += n
return ansclass Solution {
public int minSteps(int n) {
int ans = 0;
for (int p = 2; p * p <= n; p++) {
while (n % p == 0) {
ans += p;
n /= p;
}
}
if (n > 1) ans += n;
return ans;
}
}class Solution {
public:
int minSteps(int n) {
int ans = 0;
for (int p = 2; p * p <= n; p++) {
while (n % p == 0) {
ans += p;
n /= p;
}
}
if (n > 1) ans += n;
return ans;
}
};func minSteps(n int) int {
ans := 0
for p := 2; p*p <= n; p++ {
for n%p == 0 {
ans += p
n /= p
}
}
if n > 1 {
ans += n
}
return ans
}var minSteps = function(n) {
let ans = 0;
for (let p = 2; p * p <= n; p++) {
while (n % p === 0) {
ans += p;
n /= p;
}
}
if (n > 1) ans += n;
return ans;
};function minSteps(n: number): number {
let ans = 0;
for (let p = 2; p * p <= n; p++) {
while (n % p === 0) {
ans += p;
n /= p;
}
}
if (n > 1) ans += n;
return ans;
}