一.前言

又到了记录代码的时候了，这道题来自 LeetCode，只有两个键的键盘：

最初记事本上只有一个字符 ‘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

二.题解

首先说说笔者写这道题的经历吧，不怕大家笑话，这道题我足足写了 3 小时…最开始看到这道题的时候我想的是我可以将 n 以前的操作 A 的次数以次数为键用 Hashmap 存起来，然后遇到 n 的时候直接去 Hashmap 里面拿，当我去提交的时候，发现有些测试用例是过不了的，比若说 741。然后我重新思考，发现可以用递归，比如 n = 24，但是由于思考深度不够，又有一些情况没考虑到，去提交的又数次失败…

由于递归从最开始就没考虑到那种情况，因此改起来特别麻烦，而这不得不使我重新选择一条路出发。所以由此看来啊，做题之前真要静下心来思考，思考范围要广一点。

接下来就说第一种方法，我称之为数学规律法。

1.数学规律法

先举一些简单的例子：

1
2
3
4
5
6
7
8
9
当输入不同的 n 时，对应输出的值：

1 = 0
2 = 1 2 --> 2次//因为需要复制一次，粘贴一次，因此是2
7 = 1 2 3 4 5 6 7 --> 7次// 1 + 1 + 1 + 1 + 1 + 1 + 1 = 7
12 = 1 2 3 6 12 --> 6次 //2 + 1 + 2 + 2 = 7
18 = 1 2 3 6 9 18 --> 8次 //2 + 1 + 2 + 1 +2 = 8
25 = 1 2 3 4 5 10 15 20 25 --> 10次 //2 + 1 + 1 + 2 +1 + 1 + 1 + 1 = 10
741 = 35次 --> 这个待会讲

既然是数学方法，当然要运用强大的数学规律，我们仔细观察一番会发现：如果是质数那么它的最小操作次数就是它本身，对于非质数，比如说 12 ，上面得出 6 次答案的过程我们倒着看分成 3 个片段,12 <- 6 || 6 <- 3 || 3 <- 2 <- 1。

首先来看 12 <- 6 这一个片段，6 如果要成为 12 必须先全部复制再粘贴，也就是说这里会有 2 次操作；再看 6 <- 3，3 如果要成为 6 也必须先全部复制再粘贴，也会有 2 次操作；最后看 3 <- 2 <- 1 这个片段，1 如果要成为 3 需要全部复制、粘贴、粘贴，也就是要 3 次。我们再来看看这样一个东西：12 除以 2 等于 6，这里操作次数+2，6 除以 2 等于 3，这里操作次数+2，3 除以 3 等于 1，这里操作次数+3。2 + 2 + 3 = 6。你会惊奇的发现：只需要找到能整除 n 的除数，之后全部加起来就等于最后答案了。

不相信？再来试一个！25 除以 5 等于 5，操作次数+5；5 除以 5 等于 1，操作次数+5，最终答案：5 + 5 = 10。是不是感觉有点神奇？其实这就是质因数的分解，25 能分成 5 和 5。12 能分成 2 和 2 和 3 ，因此最小操作数为 7。因此最上面的 741 分解质因数为 19 和 13 和 3，所以其最小操作数为 35。

这种方法接近双百，附图：

a).数学规律法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minSteps(int n) {
        int result = 0;
        int i;
        //当 n 被分解到 1 时，退出循环
        while(n != 1){
            for( i = 2; i <= n; i++){
            //遍历找出能整除 n 的 i
                if(n % i == 0){
                    n /= i;
                    //result加上能整除 n 的 i
                    result += i;
                    i = 2;//成功整除 n 后，进行新的 i 循环，找出下一个能整除 n 的i
                }
            }
        }
    return result;
    }
}

2.动态规划(LeetCode 官方题解)

1.动态规划技巧

先简单说说动态规划的一些技巧吧。

  • 确定好 dp 数组的含义，一定要理解 dp[i]所表示的是什么
  • 动态规划的数据通常是由前面一个数据推导演变而来的，因此需要得出推导公式
  • 最后就是 dp 数组的初始化了，这个需要额外注意，因为初始化一旦有问题，就会导致最终答案出错
2.思路

举个例子，还是拿 12 来说吧，12 = 1 -> 2 -> 3 -> 6 -> 12，我们会发现要得出 12 的最小操作次数，需要知道 6 的最小操作次数再加上复制粘贴的次数（2 次），进而需要知道 3 的最小操作次数再加上复制粘贴的次数（2 次）…总的来说就是如果要找出 i 个 A ，则必定要先找到 i 的因数 j ,而后通过 i / j 次复制粘贴得到 i 个 A 因此会发现这个递推规律：
递推公式
其中， j | i 表示 j 能整除 i ，i / j 表示复制粘贴的次数。对于每一个 dp[i] 只需要等于最小的 f[j] + i / j。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int minSteps(int n) {
        int[] f = new int[n + 1];
        for (int i = 2; i <= n; ++i) {
            f[i] = Integer.MAX_VALUE;
            for (int j = 1; j <= i; ++j) {
                if (i % j == 0) {
                    f[i] = Math.min(f[i], f[j] + i / j);
                }
            }
        }
        return f[n];
    }
}