650. 只有两个键的键盘 #

问题描述#

最初在一个记事本上只有一个字符 '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] 。

解题思路#

首先最多 n 次即可得到结果，即复制一次然后粘贴 n - 1 次。

方法一：动态规划#

用 dp[cur][k] 表示记事本字符数为 cur，剪贴板的字符数为 k 时的最少操作次数 (k <= cur)。

显然 dp[cur][cur] 时剪贴板中有 cur 个字符，这 cur 个字符只能通过复制记事本已有的 cur 个字符得到，即 dp[cur][cur] = min(dp[cur][1...cur-1])。

当我们得到了 dp[cur][k] 时，我们同样可以通过一次粘贴操作得到 dp[cur + k][k] 的结果，所以遍历保存最小值即可。

Python

class Solution:
    def minSteps(self, n: int) -> int:
        dp = [[1005 for _ in range(n + 1)] for _ in range(n + 1)]

        dp[1][0] = 0
        for i in range(1, n + 1):
            dp[i][i] = 1 + min(dp[i][:i])
            for j in range(1, min(i + 1, n - i + 1)):
                dp[i + j][j] = min(dp[i + j][j], 1 + dp[i][j])

        return min(dp[n])

C++

class Solution {
public:
    int minSteps(int n) {
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 1005));

        dp[1][0] = 0;
        for (int i = 1; i <= n; ++i) {
            dp[i][i] = *min_element(dp[i].begin(), dp[i].begin() + i) + 1;
            for (int j = 1; j <= min(n - i, i); ++j) {
                dp[i + j][j] = min(dp[i + j][j], 1 + dp[i][j]);
            }
        }

        return *min_element(dp[n].begin(), dp[n].end());
    }
};

时间复杂度：\(\mathcal{O}(n^2)\)
空间复杂度：\(\mathcal{O}(n^2)\)

方法二：数学推理#

整个操作过程可以表示为 \([\text{Copy-}\text{Paste}^{a_1},\dots,\text{Copy-}\text{Paste}^{a_n}]\)，其中 \(\text{Copy}\) 表示复制一次，\(\text{Paste}^{a_i}\) 表示粘贴 \(a_i\) 次，\(\text{Copy-}\text{Paste}^{a_i}\) 的操作总次数为 \(a_i+1\) 次。

假设当前记事本的已有字符数为 \(s\) 个，复制一次后，每粘贴一次都会增加 \(s\) 个字符，则经过 \(a_i\) 次粘贴后的总字符数为 \(s \times (1 + a_i)\) 个。

所以我们要求的就是满足 \(1 \times (1+a_1) \times \dots \times (1+a_n)=n\) 时，\((1+a_1) + \dots + (1+a_n)\) 最小。

即我们所求的是将 \(n\) 因式分解后的和最小。

如果 \(n\) 的某个因子 \(c\) 可以表示为 \(c=a \times b\) 且有 \((a \ge 2, b \ge 2)\)，即 \(c\) 是个合数。因为 \(\frac{a+b}{c}=\frac{a+b}{a \times b}=\frac{1}{a} + \frac{1}{b} \le \frac{1}{2}+\frac{1}{2}=1\)，所以 \(a+b \le ab=c\)，即如果 \(c\) 是个合数，我们通过分解总可以将次数减少，所以答案即为 \(n\) 的所有素数因子之和。