题目描述：
最初在一个记事本上只有一个字符 ‘A‘。你每次可以对这个记事本进行两种操作：
Copy All (复制全部) : 你可以复制这个记事本中的所有字符(部分的复制是不允许的)。
Paste (粘贴) : 你可以粘贴你上一次复制的字符。
给定一个数字 n 。你需要使用最少的操作次数，在记事本中打印出恰好 n 个 ‘A‘。输出能够打印出 n 个 ‘A‘ 的最少操作次数。
示例 1:
输入: 3
输出: 3
解释:
最初, 我们只有一个字符 ‘A‘。
第 1 步, 我们使用 Copy All 操作。
第 2 步, 我们使用 Paste 操作来获得 ‘AA‘。
第 3 步, 我们使用 Paste 操作来获得 ‘AAA‘。
说明: n 的取值范围是 [1, 1000] 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/2-keys-keyboard
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
博主看到这个题的个人思路：
最优解，下意识的往动态规划方向思考，并且根据题目特性得出：“在此题中，我们必然会经历一次复制，并且必然存在一种解，是由n次A的粘贴操作组成”。所以，生硬的想一下dp[n] = min(a,b)。
动态方程推演：
初始格子为一个n长的int数组，此题不存在n=0的情况，从1开始，所以这个数组长度+1
int[] dp = new int[n+1];
dp[i]即储存当n=i时，此时所需要的最小次数。即答案的解。
当n=1时：dp[1]=0; （读题，最初即为‘A‘，不需要任何操作就可以满足条件，so，这里是一个)
if (n=1) {
return 0;
}
当n=2时：dp[2]=2;（复制一次，粘贴一次，后面此类将不再赘述）
...
此时发现，数字的特性：当数字可以被某个数整除时（如：9%3 == 0），那么，我们会发现，9/3=3，我们复制3份3个‘A‘，即可达到目的。但是，这个解是最优解吗？
操作次数为：
复制->粘贴->粘贴->复制->粘贴->粘贴
‘A‘->‘AA‘->‘AAA‘->‘AAA‘->‘AAAAAA‘->‘AAAAAAAAA‘
步骤6
思考一下在题目限制内，我们都有哪些操作方式：
题目要求最小次数，假如，我一次粘贴之后，9变成8，此时8可以由2个4达成。
模拟这个操作，发现不可以。
那继续想想其它情景
...
此时，突然意识到算法。数学理论、数学公式、数学概念。这些算法题，何其像当初的数学应用题啊...
这个操作，难道花里胡哨描述半天，就是数学里的最大因子求解吗？（真的是吗？）
理一下思路：
验证真理的方式，实践出真知——穷举
（Ps.越来越像解应用题了...公式或者概念记不清了就开始穷举推导...伟人都给了现成的了）
当我要求得20的最优解时，并且我的达成方式只能是复制粘贴。
那么，
1.从1开始粘贴20次，result=21
2.从1到2，然后10次，result=13
3.从1到2，从2到4？？，从4开始5次，
4.从1到2，从2到3，从3到4，从4到5，{然后从5开始4次||从5到10 【从5到10？？？】}，从10到20）
...
此时发现，最优解里我们需要其它最优解支持，
也就是说，当我们在情况3时，我们需要2到4的最优解；在情况4时，我们需要在{}中的最优解，在这里还需要【】中的最优解
这时候会不会觉得乱？其实不是，我们只需要“假设我们已经获得最优解”即可。
通过规律，我们可以较粗略的看出，随着大因子的引入，次数在慢慢下降的，
而且，我们的大因子可以帮助我们尽快的达成数值增长，而我们付出的则是达到它的代价+1次复制操作
此时带入数学思维，同时回想起，这种默认子条件为最优的“递归思想”复杂度。
也就是说，最差的情况也不过是退化掉变成持平与原方法。即4这种。
所以，我们有理由认为，最大的因子数就是我们需要的最优解
此时变化思路，开始尝试：
// 最大因子求解方法，最大，那就从一半开始向前搜索吧
// 若没有则返回1，原因是题目中必须要有结果，那么最差的值不过是其本身，也就是除数为1的时候
public int findMaxFactors(int k) {
int res = 1;
for (int i = k/2; i>=2; --i) {
if (k % i == 0) {
res = i;
break;
}
}
return res;
}
有了这个最大的因子数之后，开始思考怎么使用
求n=20为例子思考：
20的最大因子数为10，如果知道达到n=10的最小值，那么在此基础上->复制->粘贴
10的最大因子数为5，如果直到到达n=5的最小值，那么在此基础上->复制->粘贴
5的最大因子数是...5是质数，我们只能通过复制->粘贴->粘贴->粘贴->粘贴来到达，那么也就是说，其自身
以上述思路：
int count = 0; // 弄个计数器统计记录结果
while() {
int mf = findMaxFactors(n);
count += n/mf;
}
/** 此时还差个循环结束条件
* 通过上述发现，当最后的数开始变成质数的时候，也就是结束出结果的时候，即mf=1的时候
*/
int pre = n; // 记录上一个数
int count = 0;
int mf = 0;
while(pre != 1) {
mf = findMaxFactors(pre);
count += pre/mf;
pre = mf;
}
至此，去试试吧。
class Solution {
public int minSteps(int n) {
if (n == 1) {
return 0;
}
int pre = n;
int count = 0;
int mf = 0;
while(pre != 1) {
mf = findMaxFactors(pre);
count += pre/mf;
pre = mf;
}
return count;
}
// 寻找n的最大因子数
public int findMaxFactors(int k) {
int res = 1;
for (int i = k/2; i>=2; --i) {
if (k % i == 0) {
res = i;
break;
}
}
return res;
}
}
结果：
这个结果很满意了。
分析一下时间复杂度和空间复杂度吧。
同时，这道题也可以熟悉一下递归与动态规划。
递归：
class Solution {
public int minSteps(int n) {
// 递归解法
if (n == 1) {
return 0;
}
int res = n; // 质数情况
// 合数情况处理
for (int i = 2; i < n; i++) {
if (n%i == 0) {
res = Math.min(res, minSteps(i)+n/i);
}
}
return res;
}
}
运行结果：
动态规划：
class Solution {
public int minSteps(int n) {
int[] dp = new int[n+1];
Arrays.fill(dp, n);
dp[1] = 0;
for (int i=2; i<=n; ++i) {
for (int j=1; j<=i; ++j) {
if (i%j == 0) {
dp[i] = Math.min(dp[i], dp[j]+i/j);
}
}
}
return dp[n];
}
}
运行结果：
这两种解法思路如果有需要在留言吧，我想以后遇到典型些的，或者说有意义些的相关题目在总结，于此题，就当是玩玩吧。
并且感觉这递归的结果有些不正常...重复值的话，不该如此效率啊。
原文：https://www.cnblogs.com/boziyouning/p/14678779.html