0650. 只有两个键的键盘

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. 状态转移方程 #
  1. 对于 $i$ 个字符 'A',如果 $i$ 可以被一个小于 $i$ 的整数 $j$ 除尽($j$ 是 $i$ 的因子),则说明 $j$ 个字符 'A' 可以通过「复制」+「粘贴」总共 $\frac{i}{j}$ 次得到 $i$ 个字符 'A'
  2. 而得到 $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)$。
本站总访问量  次  |  您是本站第  位访问者