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
解法
方法一:记忆化搜索
定义 $dfs(i)$ 为输出 $i$ 个字符的最少操作次数。初始化 dfs(1)=0
。
当 $i\gt 1$ 时,有:
$$ dfs(i)=\min _{j \mid i} (dfs(\frac{i}{j})+j, i), 2\leq j\lt i $$
时间复杂度 $O(n\sqrt{n})$。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
方法二:动态规划
记忆化搜索也可以改成动态规划。
$$ dp[i]=\min _{j \mid i} (dp[\frac{i}{j}]+j, i), 2\leq j\lt i $$
时间复杂度 $O(n\sqrt{n})$。
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
方法三
1 2 3 4 5 6 7 8 9 10 11 12 |
|