0650. 只有两个键的键盘 #

标签：数学、动态规划
难度：中等

题目大意 #

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

Copy All（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。
Paste（粘贴）：粘贴上一次复制的字符。

现在，给定一个数字 $n$，需要使用最少的操作次数，在记事本上输出恰好 $n$ 个 'A' 。

要求：返回能够打印出 $n$ 个 'A' 的最少操作次数。

说明：

$1 \le n \le 1000$。

示例：

示例 1：

1
2
3
4
5
6
7


输入：3
输出：3
解释
最初, 只有一个字符 'A'。
第 1 步, 使用 Copy All 操作。
第 2 步, 使用 Paste 操作来获得 'AA'。
第 3 步, 使用 Paste 操作来获得 'AAA'。

示例 2：

1
2


输入：n = 1
输出：0

解题思路 #

思路 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
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


import math

class Solution:
    def minSteps(self, n: int) -> int:
        dp = [0 for _ in range(n + 1)]
        for i in range(2, n + 1):
            dp[i] = float('inf')
            for j in range(1, int(math.sqrt(n)) + 1):
                if i % j == 0:
                    dp[i] = min(dp[i], dp[j] + i // j, dp[i // j] + j)

        return dp[n]

思路 1：复杂度分析 #

时间复杂度：$O(n \sqrt{n})$。外层循环遍历的时间复杂度是 $O(n)$，内层循环遍历的时间复杂度是 $O(\sqrt{n})$，所以总体时间复杂度为 $O(n \sqrt{n})$。
空间复杂度：$O(n)$。用到了一维数组保存状态，所以总体空间复杂度为 $O(n)$。