0650. 只有两个键的键盘

0650. 只有两个键的键盘 #

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

题目大意 #

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

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

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

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

说明

  • $1 \le n \le 1000$。

示例

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

解题思路 #

思路 1:动态规划 #

1. 划分阶段 #

按照字符 'A' 的个数进行阶段划分。

2. 定义状态 #

定义状态 dp[i] 表示为:通过「复制」和「粘贴」操作,得到 i 个字符 'A',最少需要的操作数。

3. 状态转移方程 #

对于 i 个字符 'A',如果 i 可以被一个小于 j 的整数除尽(即 ji 的因子),则说明 j 个字符 'A' 可以通过「复制」+「粘贴」总共 i // j 次的得到 i 个字符 'A'

得到 j 个字符 'A',最少需要的操作数可以通过 dp[j] 获取。则我们可以枚举 i 的因子,从中找到最小的 dp[j] + i // j,即为 dp[i]。即 dp[i] = min(dp[i], dp[j] + i // j),在 i % j == 0 的条件下。

同时因为如果满足 i % j == 0,则 ji // j 都是 i 的因子,两者中必有一个因子是小于等于 $\sqrt{i}$ 的,所以在枚举 i 的因子时,我们只需要枚举区间 $[1, \sqrt{i}]$ 上 i 的因子即可。

此时状态转义方程为 dp[i] = min(dp[i], dp[j] + i // j, dp[i // j] + j),在 i % j == 0 的条件下。

4. 初始条件 #
  • i1 时,最少需要的操作数为 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)$。
本站总访问量  次  |  您是本站第  位访问者