只差一点点

这就是最好的时代

【LeetCode.650】只有两个键的键盘

分类于

题目：只有两个键的键盘

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

Copy All（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。
Paste（粘贴）：粘贴 上一次 复制的字符。
给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出 恰好 n 个 'A' 。返回能够打印出 n 个 'A' 的最少操作次数。

示例 1：

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

示例 2：

1
2
输入：n = 1
输出：0

提示：

1 <= n <= 1000

分析：

总问题可以由小问题逐步扩大得到，考虑动态规划

只有复制和粘贴两种操作，如果要得到 i ，那么就一定要先得到它的其中一个因数 j ，由 j 粘贴 i / j - 1 次得到 i

设动态规划数组 dp[i] 表示得到 i 个字母需要的最少操作次数

需要从 1 到 i - 1 寻找 i 的因数，可得状态转移方程：dp[i] = min( (1 ~ i-1) dp[j] * i/j)

初始边界条件：dp[1] = 0

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minSteps(int n) {
        vector<int> dp(n + 1);
        dp[1] = 0;
        for(int i = 2; i <= n; i++){
            dp[i] = INT_MAX;
            for(int j = 1; j * j <= i; j++){
                if(i % j == 0) {
                    dp[i] = min(dp[i], dp[j] + i / j);
                    dp[i] = min(dp[i], dp[i / j] + j);
                }
            }
        }
        return dp[n];
    }
};

时间复杂度O(n根号n)，空间复杂度O(n)

细节：

如果 j 是 i 的因数，那么 i / j 必然也是 i 的因数，因此我们只需要检测到根号 i 为止就足够了，有效降低时间复杂度