Java实现 LeetCode 650 只有两个键的键盘（递归 || 数学）

650. 只有两个键的键盘

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

class Solution {
public int minSteps(int n) {
if(n == 1){
return 0;
}
//加一个需要一步
return process(n, 1, 1) + 1;
} // 保持粘贴板有东西
private int process(final int target, int nowLen, int copyLen){
// 先粘贴
nowLen += copyLen;
if(target == nowLen){
return 1;
}
//如果能整除当前得，就是复制，因为先黏贴得一步，然后复制得一步
return (target - nowLen) % nowLen == 0 ? process(target, nowLen, nowLen) + 2 : process(target, nowLen, copyLen) + 1;//不行得话只有黏贴一步
} //加n>1时 其实就是将n分解为m个数字的乘积 且m个数字的和最小
// 即把一个数分解为n个质数的和 从小到大的去试探
// public int minSteps(int n) {
// int res = 0;
// for (int i = 2; i <= n; i++) {
// while (n % i == 0) {
// res += i;
// n /= i;
// }
// }
// return res;
// }}