LeetCode 题解工作台
两个键的键盘
最初记事本上只有一个字符 'A' 。你每次可以对这个记事本进行两种操作： Copy All （复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。 Paste （粘贴）：粘贴 上一次 复制的字符。 给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出 恰好 n 个 'A' 。返回…
2
题型
4
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
定义 为输出 个字符的最少操作次数。初始化 `dfs(1)=0`。 当 $i\gt 1$ 时，有：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
最初记事本上只有一个字符 'A' 。你每次可以对这个记事本进行两种操作：
Copy All（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。Paste（粘贴）：粘贴 上一次 复制的字符。
给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出 恰好 n 个 'A' 。返回能够打印出 n 个 'A' 的最少操作次数。
示例 1：
输入：3 输出：3 解释： 最初, 只有一个字符 'A'。 第 1 步, 使用 Copy All 操作。 第 2 步, 使用 Paste 操作来获得 'AA'。 第 3 步, 使用 Paste 操作来获得 'AAA'。
示例 2：
输入：n = 1 输出：0
提示：
1 <= n <= 1000
解题思路
方法一：记忆化搜索
定义 为输出 个字符的最少操作次数。初始化 dfs(1)=0。
当 时，有：
时间复杂度 。
class Solution:
def minSteps(self, n: int) -> int:
@cache
def dfs(n):
if n == 1:
return 0
i, ans = 2, n
while i * i <= n:
if n % i == 0:
ans = min(ans, dfs(n // i) + i)
i += 1
return ans
return dfs(n)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(\sqrt{n}) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Candidate demonstrates a strong understanding of dynamic programming and optimization techniques.
- question_mark
Candidate applies mathematical insights, considering divisors and states, to minimize operations.
- question_mark
Candidate is able to explain how state transition and factorization techniques work together.
常见陷阱
外企场景- error
Not considering the factorization of n and how it affects the number of operations.
- error
Overcomplicating the problem with unnecessary calculations or inefficient approaches.
- error
Failing to optimize for time complexity when implementing dynamic programming solutions.
进阶变体
外企场景- arrow_right_alt
Consider variations where other operations besides 'Copy All' and 'Paste' are allowed.
- arrow_right_alt
Extend the problem to handle cases with multiple characters initially on the screen.
- arrow_right_alt
Implement a solution for a larger range of n values, focusing on efficiency for large inputs.