一.前言
又到了记载代码的时间了，这道题来自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。然后我重新思考，发现可以用递归，但是由于思考深度不敷，又有一些情况没思量到，去提交的又数次失败...真的恼火。
由于递归从最开始就没思量到那种情况，因此改起来特殊贫苦，而这不得不使我重新选择一条路出发。以是由此看来啊，做题之前真要静下心来思考，思考范围要广一点。
接下来就说第一种方法，我称之为数学规律法。
1.数学规律法
先举一些简朴的例子：
当输入不同的 n 时，对应输出的值：1 = 02 = 1 2 --> 2次//由于必要复制一次，粘贴一次，因此是27 = 1 2 3 4 5 6 7 --> 7次// 1 + 1 + 1 + 1 + 1 + 1 + 1 = 712 = 1 2 3 6 12 --> 7次 //2 + 1 + 2 + 2 = 718 = 1 2 3 6 9 18 --> 8次 //2 + 1 + 2 + 1 +2 = 825 = 1 2 3 4 5 10 15 20 25 --> 10次 //2 + 1 + 1 + 2 +1 + 1 + 1 + 1 = 10741 = 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。
这种方法靠近双百，附图：
数学规律法代码
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所表现的是什么
- 动态规划的数据通常是由前面一个数据推导演变而来的，因此必要得出推导公式
- 末了就是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 表现复制粘贴的次数。对于每一个 f 只必要便是最小的 f[j] + i / j。
class Solution { public int minSteps(int n) { int[] f = new int[n + 1]; for (int i = 2; i <= n; ++i) { f = Integer.MAX_VALUE; for (int j = 1; j <= i; ++j) { if (i % j == 0) { f = Math.min(f, f[j] + i / j); } } } return f[n]; }} |
