0650. 只有两个键的键盘 #
- 标签:数学、动态规划
- 难度:中等
题目大意 #
描述:最初记事本上只有一个字符 'A'
。你每次可以对这个记事本进行两种操作:
- Copy All(复制全部):复制这个记事本中的所有字符(不允许仅复制部分字符)。
- Paste(粘贴):粘贴上一次复制的字符。
现在,给定一个数字 $n$,需要使用最少的操作次数,在记事本上输出恰好 $n$ 个 'A'
。
要求:返回能够打印出 $n$ 个 'A'
的最少操作次数。
说明:
- $1 \le n \le 1000$。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:动态规划 #
1. 划分阶段 #
按照字符 'A'
的个数进行阶段划分。
2. 定义状态 #
定义状态 $dp[i]$ 表示为:通过「复制」和「粘贴」操作,得到 $i$ 个字符 'A'
,最少需要的操作数。
3. 状态转移方程 #
- 对于 $i$ 个字符
'A'
,如果 $i$ 可以被一个小于 $i$ 的整数 $j$ 除尽($j$ 是 $i$ 的因子),则说明 $j$ 个字符'A'
可以通过「复制」+「粘贴」总共 $\frac{i}{j}$ 次得到 $i$ 个字符'A'
。 - 而得到 $j$ 个字符
'A'
,最少需要的操作数可以通过 $dp[j]$ 获取。
则我们可以枚举 $i$ 的因子,从中找到在满足 $j$ 能够整除 $i$ 的条件下,最小的 $dp[j] + \frac{i}{j}$,即为 $dp[i]$,即 $dp[i] = min_{j | i}(dp[i], dp[j] + \frac{i}{j})$。
由于 $j$ 能够整除 $i$,则 $j$ 与 $\frac{i}{j}$ 都是 $i$ 的因子,两者中必有一个因子是小于等于 $\sqrt{i}$ 的,所以在枚举 $i$ 的因子时,我们只需要枚举区间 $[1, \sqrt{i}]$ 即可。
综上所述,状态转移方程为:$dp[i] = min_{j | i}(dp[i], dp[j] + \frac{i}{j}, dp[\frac{i}{j}] + j)$。
4. 初始条件 #
- 当 $i$ 为 $1$ 时,最少需要的操作数为 $0$。所以 $dp[1] = 0$。
5. 最终结果 #
根据我们之前定义的状态,$dp[i]$ 表示为:通过「复制」和「粘贴」操作,得到 $i$ 个字符 'A'
,最少需要的操作数。 所以最终结果为 $dp[n]$。
思路 1:动态规划代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n \sqrt{n})$。外层循环遍历的时间复杂度是 $O(n)$,内层循环遍历的时间复杂度是 $O(\sqrt{n})$,所以总体时间复杂度为 $O(n \sqrt{n})$。
- 空间复杂度:$O(n)$。用到了一维数组保存状态,所以总体空间复杂度为 $O(n)$。