650. 两个键的键盘

发表于 分类于 阅读次数： Waline： 本文字数： 736 阅读时长 ≈ 2 分钟

考点

  • 线性DP
  • 数学

思路

一、问题概述

初始时记事本中仅包含一个字符 'A'。允许执行以下两种操作：

  1. Copy All：复制当前记事本中的所有字符；
  2. Paste：将剪贴板中的内容粘贴到记事本末尾。

给定目标整数 n，要求通过若干次操作，使记事本中恰好包含 n 个 'A'，并最小化操作次数。

二、状态定义

定义一维动态规划数组： \[ f[x] = \text{得到恰好 } x \text{ 个 } A \text{ 的最少操作次数} \] 该定义具有以下特点：

  • 状态仅与当前字符数量有关；
  • 剪贴板内容不显式建模，而是通过转移过程隐含表示；
  • 所有有效策略都可以拆解为若干次“复制一次 + 粘贴若干次”的组合。

三、初始状态

初始时，记事本中已经有一个 'A'，不需要任何操作，因此： \[ f[1] = 0 \] 其余状态初始化为一个极大值，表示尚不可达或尚未更新。

四、状态转移方程

1. 操作序列的结构分析

若当前记事本中有 i 个 'A'，可以执行如下操作序列：

  • 先执行一次 Copy All（代价 +1）；
  • 再连续执行 j 次 Paste（代价 +j）。

此时，字符数将变为： \[ k = i + j \times i = i (j + 1) \] 即：从 i 扩展到 k，总操作次数为 1 + j。

2. 转移方程

只要 k ≤ n，就可以从状态 i 转移到状态 k，得到转移方程： \[ f[k] = \min\bigl(f[k],\; f[i] + 1 + j\bigr) \] 其中：

  • i 表示当前字符数；
  • j 表示粘贴次数；
  • k = i + j * i 为转移后的字符数。

通过枚举 i 和 j，可以覆盖所有合法的状态转移。

3. 枚举方式说明

  • 外层枚举当前状态 i；
  • 内层枚举粘贴次数 j ≥ 1；
  • 当 i + j * i > n 时停止枚举。

这种枚举方式等价于按因子关系进行转移，但实现上更加直接，避免了显式枚举因子。

五、答案构成

最终目标是得到恰好 n 个 'A' 的最少操作次数，因此答案为： \[ \boxed{f[n]} \]

六、算法复杂度分析

  • 时间复杂度： \[ O\!\left(\sum_{i=1}^{n} \frac{n}{i}\right) = O(n \log n) \]

  • 空间复杂度： \[ O(n) \]

在 n ≤ 1000 的约束下，该算法效率充足。

七、AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    static const int maxn = 1e3 + 5;

    int minSteps(int n) {
        int f[maxn];

        // 初始化为无穷大，表示尚未可达
        memset(f, 0x3f, sizeof(f));

        // 初始状态：已经有 1 个 'A'，不需要任何操作
        f[1] = 0;

        // 枚举当前屏幕上的字符数 i
        for (int i = 1; i <= n; ++i) {

            // 在 i 的基础上：先 Copy All 一次，再 Paste j 次
            // 新字符数 k = i + j * i
            for (int j = 1; i + j * i <= n; ++j) {
                int k = i + j * i;

                // 转移：f[i] + 1（Copy） + j（Paste）
                f[k] = min(f[k], f[i] + 1 + j);
            }
        }

        // 目标状态
        return f[n];
    }
};