650. 只有两个键的键盘

题目

最初记事本上只有一个字符 ‘A’ 。你每次可以对这个记事本进行两种操作：

Copy All（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。
Paste（粘贴）：粘贴 上一次 复制的字符。
给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出 恰好 n 个 ‘A’ 。返回能够打印出 n 个 ‘A’ 的最少操作次数。

示例 1：

输入：3
输出：3
解释：
最初, 只有一个字符 ‘A’。
第 1 步, 使用 Copy All 操作。
第 2 步, 使用 Paste 操作来获得 ‘AA’。
第 3 步, 使用 Paste 操作来获得 ‘AAA’。

示例 2：

输入：n = 1
输出：0

提示：

1 <= n <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/2-keys-keyboard
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这其实是一个数学题，也能用动态规划，不过感觉没有数学法更直接优雅。

先说动态规划思路，其实也体现了数学思想，假设要得到n个字母，可以通过已经有的k个字母，复制一次，然后粘贴若干次得到。因为每一步都是k的倍数，那么必须满足k是n的因子。因此可以枚举n的因子，可以得到#card=math&code=dp%5Bi%5D%20%3D%20min%28dp%5Bj%5D%20%2B%20i%20%2F%20j%29&id=zXcVf)，其中j是i的因子。可以写出下面的代码一。

代码

DP 代码一

class Solution {
    public int minSteps(int n) {
        int[] dp = new int[n + 1];
        for (int i = 2; i < n + 1; i++) {
            dp[i] = n;
            for (int j = 1; j < i; j++) {
                if (i % j == 0) {
                    dp[i] = Math.min(dp[i], dp[j] + i / j);
                }
            }
        }
        return dp[n];
    }
}

DP 优化 代码二

代码一的时间复杂度是，其实内层循环的j可以只枚举到#card=math&code=sqrt%28i%29&id=dCYhq)，因为尽管大于，但是也已经计算过了。

class Solution {
    public int minSteps(int n) {
        int[] dp = new int[n + 1];
        for (int i = 2; i < n + 1; i++) {
            dp[i] = n;
            for (int j = 1; j * j <= i; j++) {
                if (i % j == 0) {
                    dp[i] = Math.min(dp[i], dp[j] + i / j);
                    dp[i] = Math.min(dp[i], dp[i / j] + j);
                }
            }
        }
        return dp[n];
    }
}

数学 分解质因数 代码三

看「官解法二」讲的比较清楚。

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