650. 只有两个键的键盘——【Leetcode每日一题】

650. 只有两个键的键盘

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

提示：

• 1 <= n <= 1000

思路：(动态规划)

1. 动态规划问题最重要的是先确定一共有哪些状态；
2. 然后分析每种状态的关系，从而确定 状态转移方程。

第一步：确定所有的状态：

随意看其中的一步，就两种状态，不是先复制记事本字符的全部再粘贴，就是粘贴已经在粘贴板上的：

• 1、复制再粘贴
• 2、粘贴

第二步：分析每种状态的关系，确定状态转移方程：

• 1、复制再粘贴：只有当前记事本上的字符数，是目标数的因子，即能整除目标数，此时才能复制完，再粘贴，进而能得到目标数；

  • 复制一次+粘贴一次，此时的操作数总数+2，即总操作数为: $$ans+=2$$
  • 粘贴板上字符的长度为复制前记事本上的字符数，即粘贴板上字符数为：$$paste=num$$
  • 粘贴后记事本上的字符数要加上粘贴的字符数，即完成一次复制粘贴记事本上的字符数为：$$num+=paste$$

• 2、粘贴，此时记事本上的字符数不能整除目标数，则复制当前记事本上的长度一定到达不了目标数，则 只能粘贴已经在粘贴板上的字符：

  • 只粘贴一次，总操作数+1，即总操作数为: $$ans+=1$$
  • 粘贴后记事本上的字符数要加上粘贴的字符数，即完成一次粘贴记事本上的字符数为：$$num+=paste$$

代码：(Java)

public class MInSteps {public static void main(String[] args) {// TODO Auto-generated method stubint n = 3;System.out.println(minSteps(n));}public static int minSteps(int n) {if(n == 1) {return 0;}int num = 2;//至少两个字符,从两个字符开始int ans = 2;//总操作数,两个字符时，已经复制粘贴各一次，且此时粘贴板上有一个字符了int paste = 1; //复制板上的字符数while(num < n) {if(n % num == 0) {ans += 2; //复制 + 粘贴paste = num;}else {ans += 1; //粘贴}num += paste;//当前数+粘贴板上字符数}return ans;}
}

运行结果：

力扣提交：

复杂度分析：

• 时间复杂度：$O(n)$，最坏的情况n是质数，一次只能粘贴一次，要粘贴n次。
• 空间复杂度：$O(1)$，只需要常数级别的空间。

注：仅供学习参考， 如有不足，欢迎指正！

题目来源：力扣。