最初在一个记事本上只有一个字符 '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] 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/2-keys-keyboard
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
第一反应是二维DP
dp[i][j] 表示总共i个字母 粘贴板有j个字母 的最小步骤
class Solution { public: int minSteps(int n) { // dp[i][j] 总共i个字母 粘贴板有j个字母 的最小步骤 int dp[n+1][n+1]; memset(dp, -1, sizeof dp); dp[1][0] = 0; int ans = -1; for (int i = 1; i <= n; i++) { for (int j = 0; j <= i; j++) { if (dp[i][j] != -1) { if (dp[i][i] == -1 || dp[i][i] > dp[i][j] + 1) { dp[i][i] = dp[i][j] + 1; } if (i + j <= n && (dp[i + j][j] == -1 || dp[i + j][j] > dp[i][j] + 1)) { dp[i + j][j] = dp[i][j] + 1; } } if (i == n && dp[i][j] != -1 && (ans == -1 || ans > dp[i][j])) { ans = dp[i][j]; } } } return ans; } };
不过运行速度有点慢……
对于任何一个数 n，都可以先凑到该数的一个因数 x ，然后 copy all 复制 n/x-1 次，枚举因数即可
如果 n 为质数，就只能使用 1 来复制 n-1 次
class Solution { public: int minSteps(int n) { int dp[n+1] = {0}; for (int i = 2; i <= n; i++) { dp[i] = i; for (int j = 1; j < i; j++) { if (i % j == 0) { dp[i] = min(dp[i], dp[j] + i / j); } } } return dp[n]; } };
复杂度和上面一样，O(n^2) 不过可以优化一下
考虑到一个数x=p*q， p和q是两个质数，那么总共打印的次数就是先打印 p 个字母 然后复制 q 次，或者先打印 q 个字母，复制 p 次，结果都是一样的 p+q
在 p > 1 且 q > 1 的条件下 p*q >= p+q 永远成立，所以先打印因数个字母再复制的打印方法是最优的。
所以将n做质因数分解就可以了，比如 36=2*2*3*3 答案就是 dp[36]=dp[2]+dp[2]+dp[3]+dp[3]，又知道所有的质数答案都是固定的（即该数本身），也就是说 36=2+2+3+3=10
class Solution { public: int minSteps(int n) { int ans = 0; for (int i = 2; i <= n; i++) { while (n % i == 0) { n /= i; ans += i; } } return ans; } };