脚本宝典收集整理的这篇文章主要介绍了[LeetCode] 650. 2 Keys Keyboard，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

There is only one character 'A' on the screen of a notepad. You can PErform two operations on this notepad for each step:

• Copy All: You can copy all the characters PResent on the screen (a partial copy is not Allowed).
• Paste: You can paste the characters which are copied last time.

Given an integer n, return the minimum number of operations to get the character 'A' exactly n times on the screen.

Example 1:

Input: n = 3
Output: 3
Explanation: IntITally, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.

Example 2:

Input: n = 1
Output: 0

Constraints:

• 1 <= n <= 1000

只有两个键的键盘。

最初记事本上只有一个字符 'A' 。你每次可以对这个记事本进行两种操作：

Copy All（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。Paste（粘贴）：粘贴 上一次 复制的字符。给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出 恰好 n 个 'A' 。返回能够打印出 n 个 'A' 的最少操作次数。

来源：力扣（LeetCode）链接：https://leetcode-cn.COM/problems/2-keys-keyboard著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题的思路是动态规划。注意题意，一开始已经给定了一个A。为了最后得到 N 个 A，我们其实是有多种办法的，我参考了这个帖子。最直接的办法就是 copy 一次，然后 paste N - 1 次。但是这个方法是可以被优化的。举个例子，当 N = 4 的时候，这里有两种做法，一种是需要 copy 一次 A，paste 三次得到 AAAA；另一种是需要 copy 一次 A，paste 一次得到 AA，再 copy 一次（AA），再 paste 一次得到 AAAA。这里面其实是有规律可循的。规律的细节可以直接参见我参考的帖子，但是我这里一句话总结：如果 N 可以被之前某一个比 N 小的数字整除，那么为了最后得到 N 个字母 A，是有可能只需要更少的操作次数的。

时间O(n^2)

空间O(n)

Java实现

 1 class Solution {
 2     public int minSteps(int n) {
 3         int[] dp = new int[n + 1];
 4         for (int i = 2; i <= n; i++) {
 5             dp[i] = i;
 6             for (int j = i - 1; j > 1; j--) {
 7                 dp[i] = Math.min(dp[i], dp[j] + i / j);
 8             }
 9         }
10         return dp[n];
11     }
12 }

LeetCode 题目总结

脚本宝典总结

以上是脚本宝典为你收集整理的[LeetCode] 650. 2 Keys Keyboard全部内容，希望文章能够帮你解决[LeetCode] 650. 2 Keys Keyboard所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。