一.前言
又到了记录代码的时候了，这道题来自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 = 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 --> 7次 //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
首先来看 12 6 如果要成为 12 必须先全部复制再粘贴，也就是说这里会有2次操作；再看 6 3 如果要成为 6 也必须先全部复制再粘贴，也会有2次操作；最后看 3 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 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 表示复制粘贴的次数。对于每一个 f[i] 只需要等于最小的 f[j] + i / j。
class Solution {
public int minSteps(int n) {
int[] f = new int[n + 1];
for (int i = 2; i 转载请注明：OBA博客 » 算法练习：只有两个键的键盘（数学法，动态规划）