跳转至

LeetCode: 650. 只有两个键的键盘

1、题目描述

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

Copy All (复制全部) : 你可以复制这个记事本中的所有字符(部分的复制是不允许的)。 Paste (粘贴) : 你可以粘贴你上一次复制的字符。 给定一个数字 n 。你需要使用最少的操作次数,在记事本中打印出恰好 n'A'。输出能够打印出 n'A' 的最少操作次数。

示例 1:

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

说明:

  • n 的取值范围是 [1, 1000]

2、解题思路

  • 判断当前点能够利用前面的哪些点进行复制粘贴操作,主要针对于约数
class Solution:
    def minSteps(self, n: int) -> int:
        dp = [0] * (n + 1)

        for i in range(2, n + 1):
            temp = i
            for j in range(1, i):
                if i % j == 0:
                    temp = min(temp, dp[j] + i // j)
            dp[i] = temp
        return dp[n]
  • 从2开始除,判断当前元素能够被谁整除,就进行多次的复制粘贴操作
class Solution:
    def minSteps(self, n: int) -> int:
        res = 0
        divisor = 2

        while n > 1:
            if n % divisor == 0:
                n //= divisor
                res += divisor
            else:
                divisor += 1
        return res