只有两个键的键盘 图解题解

复制粘贴凑出 n 个 A，最少按几次

给一个正整数 n，屏幕初始只有 1 个 A。每次操作二选一：复制全部内容到剪贴板，或把剪贴板内容粘贴一次接到末尾。求最少多少次操作让屏幕恰好是 n 个 A。题面给三组：n=3 要 3 次，n=1 要 0 次，n=9 要 6 次。

为什么把每次复制粘贴都试一遍会爆

顺题意最容易想到把操作序列一步步试：每步要么复制、要么粘贴，铺开成一棵树往下搜哪条路最先凑够 n 个 A。可复制时机选择很多、序列长度没有上界，搜索树指数级膨胀，n 稍大就搜不完。浪费在于同一个中间长度被不同路径反复凑到，没记下来复用。

把长度扩大 d 倍，为什么正好花 d 步

别盯着一次次按键，看一整段操作。屏幕长度要变大，唯一办法是先复制一次、再连续粘贴若干次。当前有 k 个 A，复制 1 次后每粘贴一次多 k 个，粘贴 d-1 次总共变成 k 乘 d，即扩大到 d 倍。这一段花复制 1 次加粘贴 d-1 次，正好 d 次。

所以凑出 n 个 A，本质是把 n 写成若干个大于 1 的整数连乘，每个乘数 d 花掉 d 步，总步数就是这些乘数相加，求最少操作即找乘数之和最小的拆法。

dp 为什么沿因子转移，答案为什么是质因子和

把想法写成递推。设 dp[x] 是从 1 个 A 凑到 x 个 A 的最少操作。凑到 x 的最后一段是把某个因子 m 扩大到 x（m 能整除 x），倍数 x/m、花 x/m 步，接在 dp[m] 后。枚举 x 的所有因子取最小，dp[x]=min(dp[m]+x/m)。

把 n 拆成 a 乘 b 两段共花 a+b 步；只要 a、b 都不小于 2，就有 a+b 不超过 a 乘 b（比如 2+3=5 ≤ 2×3=6）。所以因子只要还是合数、还能再拆，拆开总步数只会不增。一路拆到剩下全是质数，各段之和最小，答案就是 n 的全部质因子相加。代码不必开 dp 数组，从最小质数试除 n，除得尽就累加进答案，时间 O(√n)。

拿 n=9 把因子拆法亲手走一遍

dp[1]=0，先看 dp[3]：因子只有 1，把 1 扩到 3 倍花 3 步，dp[3]=3。到 dp[9]，因子有 1 和 3：走 1 是扩到 9 倍花 9 步得 9；走 3 是把 3 扩到 3 倍花 3 步、接在 dp[3]=3 后得 3+3=6，取小的 6，dp[9]=6，和题面对上。

换质因数分解看更快：9=3 乘 3，两个质因子相加 3+3=6。再看 n=3 本身是质数、只有 3 一个质因子，答案 3；n=1 没有质因子，答案 0——都和题面一致。

试除到 √n 就够，n=1 和质数两处别写错

试除只需从 2 到 √n：大于 √n 的因子至多剩一个，循环后若剩下的数还大于 1，把它当最后一个质因子补加，时间 O(√n)、空间 O(1)。

n=1 是头号陷阱——没有质因子，答案就是 0，别顺手返回 1。质数（7、13 这种）也容易漏，√n 以内没有因子整除它，循环一次都不加，全靠结尾那句『剩下的数大于 1 就补进来』兜住。还有个手滑：收因子时加的是因子 d 本身、不是次数 1，写成加 1 会把答案压小。

Python

class Solution:
    def minSteps(self, n: int) -> int:
        ans = 0
        d = 2
        while d * d <= n:
            while n % d == 0:
                ans += d
                n //= d
            d += 1
        return ans + (n if n > 1 else 0)

C++

class Solution {
public:
    int minSteps(int n) {
        int ans = 0;
        for (int d = 2; d * d <= n; ++d) {
            while (n % d == 0) { ans += d; n /= d; }
        }
        return ans + (n > 1 ? n : 0);
    }
};

Java

import java.util.*;
class Solution {
    public int minSteps(int n) {
        int ans = 0;
        for (int d = 2; d * d <= n; d++) {
            while (n % d == 0) { ans += d; n /= d; }
        }
        return ans + (n > 1 ? n : 0);
    }
}