LeetCode 第650题
Initially on a notepad only one character 'A' is present. You can perform two operations on this notepad for each step:
- Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
- Paste: You can paste the characters which are copied last time.
Given a number n. You have to get exactly n 'A' on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n 'A'.
题目的意思就是在一个文本编辑器里，有个一字符A，而你的键盘上只有两个按键，复制全部和粘贴， 现在要获得 n 个A,问你最少需要按多少次按键才能获得
n的范围为[1, 1000];
这道题在Leetcode上的分类为动态规划，那么我就尝试使用动态规划，自底向上递推的做。
class Solution {
public:
int minSteps(int n) {
vector<int> dp(n + 1, 0x7FFFFFFF);
vector<int> clipBoard(n + 1, 0);
dp[1] = 0;
dp[2] = 2;
clipBoard[2] = 1;
for (int i = 2; i <= n; ++i) {
int currClipBoard = clipBoard[i];
int j = i;
for (int j = i, step = 1; j + currClipBoard <= n; ++step, j+=currClipBoard) {
if (dp[j + currClipBoard] > dp[i] + step) {
dp[j + currClipBoard] = dp[i] + step;
clipBoard[j + currClipBoard] = currClipBoard;
}
}
if (i * 2 <= n && dp[i * 2] > dp[i] + 2) {
dp[i * 2] = dp[i] + 2;
clipBoard[i * 2] = i;
}
}
return dp[n];
}
};
这个解法分为两步
- 查看获得 i 个A时剪贴板上A的个数 currClipBoard, 然后看以这个剪贴板进行粘贴能不能更新后面的k个A的次数。
- 以目前的 i 个A为起点，复制 i 个A到剪贴板，看能否更新后续的 i * 2 个 A的次数
dp[n] 就是结果。
最终结果是通过了。
然后在Discussion区中发现了一个更加高明的做法，代码也很简洁。
class Solution {
public:
int minSteps(int n) {
if (n == 1) return 0;
for (int i = 2; i < n; i++)
if (n % i == 0) return i + minSteps(n / i);
return n;
}
};
我尝试解释这段代码的含义：
不难证明，如果n为质数，我们只能够通过n次操作来获得n个A，例如
n = 2 : 复制， 粘贴
n = 3 : 复制， 粘贴，粘贴。
n = 5 : 复制， 粘贴 *4
因为 n 为质数时，它的因数只有 1 和 本身，所以 n 为质数时，只能够通过复制 第一个 A， 然后通过 n -1 次粘贴来获得。
所以我们可以看出，想要把 x 个A扩展成 kx 个的话，如果 k 为 素数的话，最少需要 k 个按键操作才能实现。
那如果 n 不为 素数呢？
我们可以 把 n 划分成两个数的乘积 n = a * b;
那么 f(n) = f(a) + b;
那么b要怎么取呢？
我们假设b取的是合数（即可以拆成两个或多个的乘积）。我们假设b能够拆成2个素数的乘积 (b = m*n)
由于所有的素数都大于1。对于下面的公式是恒成立的：
m * n >= m + n;
所以 对于 b的选择来说，我们应该选择素数。
即对于b为合数的情况
f(a) + b > f(a) + m + n = f(a*m) + n
b的选择就已经很明显了。
于是问题转化为对n进行分解，分解成k个素数的乘积，然后求这k个素数的和。
这也是Discussion中算法的原理。