https://leetcode.com/problems/2-keys-keyboard/description/
http://www.cnblogs.com/grandyang/p/7439616.html
https://leetcode.com/problems/2-keys-keyboard/discuss/105899/Java-DP-Solution
X. https://leetcode.com/problems/2-keys-keyboard/discuss/105928/JavaC%2B%2B-Clean-Code-with-Explanation-4-lines-No-DP
https://blog.csdn.net/u011026968/article/details/79890311
这里有个证明 https://leetcode.com/problems/2-keys-keyboard/discuss/105900/C++-O(sqrt(n))-DP-and-greedy-prime-number-solution
里面a + b <= ab 稍微解释下：
1/b + 1/a <=1 而 a>=2 b>=2 所以成立
int minSteps(int n) {
if (n == 1) return 0;
vector<int> dp(n+1, 0);
// dp[1] = 1;
dp[2] = 2;
return dfs(dp, n);
}
int dfs(vector<int>&dp, int x) {
if (dp[x] ) return dp[x];
int ans = x;
for (int i = 2; i <= sqrt(x); i++) {
if (x % i == 0) {
ans = min( ans, dfs(dp, x/i) + i );
ans = min( ans, dfs(dp, i) + x/i );
}
}
dp[x] = ans;
return dp[x];
}
https://blog.csdn.net/TheSnowBoy_2/article/details/76722359
两种操作使得问题变得较为简单，因为状态空间因此被简化了。
所以，我们先来确定解决该问题需要用什么样的算法思想呢？
【缩小规模】首先我们规模为n的问题，分解为小的问题进行求解。比如，求得到m (m < n)个“A”需要最少操作为多少呢？
【确定依赖的关系、方向】假设我们已经得到了得到m个“A”的最少操作，那么我们能否断定规模为 n的问题 依赖于 规模为m 的问题呢？
事实上，是可能存在依赖关系的。比如 2m = n的情况。（这里【关键】只要可能存在依赖，那么我们就定义其为依赖）
方向也是很重要的一方面，大的问题依赖于小的问题，而不是小的问题依赖于大的问题。
由不同规模的问题方向上的依赖性，我们可以确定：
该问题比较适合 动态规划类、分治法 算法求解。
【排除分治法】而分治法适合将一个问题，分解成几个大小相等的问题。分治法在这里不适合，因为我们把问题分解成了底层的小问题，这些问题有重叠。
【动态规划】当子问题存在重叠的时候，这就非常适合使用动态规划进行求解了，因为动态规划的备忘录就是为了避免子问题重叠而进行重复计算的。接下来给出相应的关键定义：
dp[i] : 表示得到 i 个 “A”需要的最小操作次数。
状态转移方程 dp[i] = Min ( dp[ i ] / dp[ j ] + dp[ j ] ) , dp[ i ] 需能整除 dp[j] 且 j < i。
https://discuss.leetcode.com/topic/97590/java-dp-solution
https://leetcode.com/articles/2-keys-keyboard/
Approach #1: Prime Factorization [Accepted]
We look for a divisor
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'.
Example 1:
Input: 3 Output: 3 Explanation: Intitally, we have one character 'A'. In step 1, we use Copy All operation. In step 2, we use Paste operation to get 'AA'. In step 3, we use Paste operation to get 'AAA'.
Note:
- The
nwill be in the range [1, 1000].
http://www.cnblogs.com/grandyang/p/7439616.html
这道题就是给了我们复制和粘贴这两个按键，然后给了我们了一个A，我们的目标时利用这两个键来打印出n个A，注意复制的时候时全部复制，不能选择部分来复制，然后复制和粘贴都算操作步骤，问我们打印出n个A需要多少步操作。对于这种有明显的递推特征的题，我们要有隐约的感觉，一定要尝试递归和DP。递归解法一般接近于暴力搜索，但是有时候是可以优化的，从而能够通过OJ。而一旦递归不行的话，那么一般来说DP这个大杀器都能解的。还有一点，对于这种题，找规律最重要，DP要找出递推公式，而如果无法发现内在的联系，那么递推公式就比较难写出来了。所以，我们需要从简单的例子开始分析，试图找规律：
当n = 1时，已经有一个A了，我们不需要其他操作，返回0
当n = 2时，我们需要复制一次，粘贴一次，返回2
当n = 3时，我们需要复制一次，粘贴两次，返回3
当n = 4时，这就有两种做法，一种是我们需要复制一次，粘贴三次，共4步，另一种是先复制一次，粘贴一次，得到AA，然后再复制一次，粘贴一次，得到AAAA，两种方法都是返回4
当n = 5时，我们需要复制一次，粘贴四次，返回5
当n = 6时，我们需要复制一次，粘贴两次，得到AAA，再复制一次，粘贴一次，得到AAAAAA，共5步，返回5
通过分析上面这6个简单的例子，我想我们已经可以总结出一些规律了，首先对于任意一个n(除了1以外)，我们最差的情况就是用n步，不会再多于n步，但是有可能是会小于n步的，比如n=6时，就只用了5步，仔细分析一下，发现时先拼成了AAA，再复制粘贴成了AAAAAA。那么什么情况下可以利用这种方法来减少步骤呢，分析发现，小模块的长度必须要能整除n，这样才能拆分。对于n=6，我们其实还可先拼出AA，然后再复制一次，粘贴两次，得到的还是5。分析到这里，我想解题的思路应该比较清晰了，我们要找出n的所有因子，然后这个因子可以当作模块的个数，我们再算出模块的长度n/i，调用递归，加上模块的个数i来更新结果res即可
int minSteps(int n) { if (n == 1) return 0; int res = n; for (int i = n - 1; i > 1; --i) { if (n % i == 0) { res = min(res, minSteps(n / i) + i); } } return res; }
int minSteps(int n) {
vector<int> dp(n + 1, 0);
for (int i = 2; i <= n; ++i) {
dp[i] = i;
for (int j = i - 1; j > 1; --j) {
if (i % j == 0) {
dp[i] = min(dp[i], dp[j] + i / j);
}
}
}
return dp[n];
}
下面我们来看一种省空间的方法，我们不需要记录每一个中间值，而是通过改变n的值来实时累加结果res
int minSteps(int n) { int res = 0; for (int i = 2; i <= n; ++i) { while (n % i == 0) { res += i; n /= i; } } return res; }X.
https://leetcode.com/problems/2-keys-keyboard/discuss/105899/Java-DP-Solution
public int minSteps(int n) {
int[] dp = new int[n+1];
for (int i = 2; i <= n; i++) {
dp[i] = i;
for (int j = i-1; j > 1; j--) {
if (i % j == 0) {
dp[i] = dp[j] + (i/j);
break;
}
}
}
return dp[n];
} public int minSteps(int n) { int[] dp = new int[n + 1]; for (int i = 2; i <= n; i++) { if (i % 2 == 0) { dp[i] = dp[i / 2] + 2; } else { for (int j = i / 2; j > 0; j--) { if (i % j == 0) { dp[i] = dp[j] + i/j; break; } } } } return dp[n]; }X. https://leetcode.com/problems/2-keys-keyboard/discuss/105928/JavaC%2B%2B-Clean-Code-with-Explanation-4-lines-No-DP
- It take
2ops to double,3ops to triple, ... - if
n % 2 == 0, thenf(n) = f(n/2) + 2 - if
n % 3 == 0, thenf(n) = f(n/3) + 3 2 * 2 = 2 + 2;2 * 3 > 2 + 3;4 * 4 > 4 + 4; so it is always better to divide whenever possible.- now it became a problem for finding all possible factors;
so it is always better to divide whenever possible * It take 2 op to double, 3 ops to triple, ...
* if n % 2 == 0, then f(n) = f(n/2) + 2
* if n % 3 == 0, then f(n) = f(n/3) + 3
* 2 * 2 = 2 + 2, 2 * 3 > 2 + 3, 4 * 4 > 4 + 4, so it is always better to divide whenever possible.
* now it became a problem for finding all possible factors;
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;
}https://blog.csdn.net/u011026968/article/details/79890311
这里有个证明 https://leetcode.com/problems/2-keys-keyboard/discuss/105900/C++-O(sqrt(n))-DP-and-greedy-prime-number-solution
里面a + b <= ab 稍微解释下：
1/b + 1/a <=1 而 a>=2 b>=2 所以成立
int minSteps(int n) {
if (n == 1) return 0;
vector<int> dp(n+1, 0);
// dp[1] = 1;
dp[2] = 2;
return dfs(dp, n);
}
int dfs(vector<int>&dp, int x) {
if (dp[x] ) return dp[x];
int ans = x;
for (int i = 2; i <= sqrt(x); i++) {
if (x % i == 0) {
ans = min( ans, dfs(dp, x/i) + i );
ans = min( ans, dfs(dp, i) + x/i );
}
}
dp[x] = ans;
return dp[x];
}
https://blog.csdn.net/TheSnowBoy_2/article/details/76722359
两种操作使得问题变得较为简单，因为状态空间因此被简化了。
所以，我们先来确定解决该问题需要用什么样的算法思想呢？
【缩小规模】首先我们规模为n的问题，分解为小的问题进行求解。比如，求得到m (m < n)个“A”需要最少操作为多少呢？
【确定依赖的关系、方向】假设我们已经得到了得到m个“A”的最少操作，那么我们能否断定规模为 n的问题 依赖于 规模为m 的问题呢？
事实上，是可能存在依赖关系的。比如 2m = n的情况。（这里【关键】只要可能存在依赖，那么我们就定义其为依赖）
方向也是很重要的一方面，大的问题依赖于小的问题，而不是小的问题依赖于大的问题。
由不同规模的问题方向上的依赖性，我们可以确定：
该问题比较适合 动态规划类、分治法 算法求解。
【排除分治法】而分治法适合将一个问题，分解成几个大小相等的问题。分治法在这里不适合，因为我们把问题分解成了底层的小问题，这些问题有重叠。
【动态规划】当子问题存在重叠的时候，这就非常适合使用动态规划进行求解了，因为动态规划的备忘录就是为了避免子问题重叠而进行重复计算的。接下来给出相应的关键定义：
dp[i] : 表示得到 i 个 “A”需要的最小操作次数。
状态转移方程 dp[i] = Min ( dp[ i ] / dp[ j ] + dp[ j ] ) , dp[ i ] 需能整除 dp[j] 且 j < i。
https://discuss.leetcode.com/topic/97590/java-dp-solution
public int minSteps(int n) {
int[] dp = new int[n+1];
for (int i = 2; i <= n; i++) {
dp[i] = i;
for (int j = i-1; j > 1; j--) {
if (i % j == 0) {
dp[i] = dp[j] + (i/j);
break;
}
}
}
return dp[n];
}https://leetcode.com/articles/2-keys-keyboard/
Approach #1: Prime Factorization [Accepted]
We can break our moves into groups of
(copy, paste, ..., paste). Let C denote copying and Pdenote pasting. Then for example, in the sequence of moves CPPCPPPPCP, the groups would be [CPP][CPPPP][CP].
Say these groups have lengths
g_1, g_2, .... After parsing the first group, there are g_1 'A's. After parsing the second group, there are g_1 * g_2 'A's, and so on. At the end, there are g_1 * g_2 * ... * g_n 'A's.
We want exactly
N = g_1 * g_2 * ... * g_n. If any of the g_i are composite, say g_i = p * q, then we can split this group into two groups (the first of which has one copy followed by p-1 pastes, while the second group having one copy and q-1 pastes).
Such a split never uses more moves: we use
p+q moves when splitting, and pq moves previously. As p+q <= pq is equivalent to 1 <= (p-1)(q-1), which is true as long as p >= 2 and q >= 2.
Algorithm By the above argument, we can suppose
g_1, g_2, ... is the prime factorization of N, and the answer is therefore the sum of these prime factors.
Time Complexity: . When
N is the square of a prime, our loop does steps.
public int minSteps(int n) {
int ans = 0, d = 2;
while (n > 1) {
while (n % d == 0) {
ans += d;
n /= d;
}
d++;
}
return ans;
}
https://leetcode.com/problems/2-keys-keyboard/discuss/105897/loop-best-case-logn-no-dp-no-extra-space-no-recursion-with-explanationWe look for a divisor
d so that we can make d copies of (n / d) to get n
The process of making
d copies takes d steps (1 step of Copy All and d - 1 steps of Paste)
We keep reducing the problem to a smaller one in a loop.
The best cases occur when
n is decreasing fast, and method is almost O(log(n))
For example, when
n = 1024 then n will be divided by 2 for only 10 iterations, which is much faster than O(n) DP method.
The worst cases occur when
n is some multiple of large prime, e.g. n = 997 but such cases are rare. public int minSteps(int n) {
int s = 0;
for (int d = 2; d <= n; d++) {
while (n % d == 0) {
s += d;
n /= d;
}
}
return s;
}
Point 1: the whole steps will be like this:
CP..P CP..P CP..P. So in each segment, it's always like oneC with >=1's P. The answer is the length of this character array.
Point 2: once you reach to a non-divisor of
n at the end of any segment, it's impossible to reach n anymore. The reason is: once you reach y at the end of segment, then all future operations lead to a number that is a multiple of y, but n is not a multiple of y, so it's impossible to reach n. This means you have to make sure that each segment leads to a number that is a divisor of n.
Point 3: there are many divisors to choose, which include
n itself (corresponding to CPPP..PPP array with n-1 P). The best solution must choose one of them. Here we say the best solution always choose divisor that is not the special divisor n, because compared to the special divisor n, there is always a better divisor y to choose where 1<y<=sqrt(n) (if such y exists). If we choose n, then the length is one C and n-1 P so length is n. If we choose y where 1<y<=sqrt(n), then the length is at most y + (n / y) because there is at least one solution CPP..P CPP..P with first segment y-1 number of P, and second segment n/y - 1 number of P. With y's constraint, after some steps, we can see this length is always <=n. So if such y exists, then the best solution will choose one such y. This is the only "optimizing" step in the whole proof.
Point 4: we will reach to a point that it's always best to choose a prime divisor because non-prime divisor will continue the above process until no such
y exists, or n becomes prime number.
Point 5: so the best solution must begin with a segment that leads to a prime divisor of
n. For example, if n is 60, then the best solution either begins with a segment that reaches 2, or begins with a segment that reaches 3, or 5.
Point 6: once you reach to a divisor
y through steps A=CP...P, then we just do new_n = n/y because we can attach array A as prefix to the array of new_n's solution array.
Point 7: with the above point, then the whole solution array of
n is like this: one segment that reaches one prime divisor y, get a new n from n/y, then get another segment that reaches one prime divisor w (probably w=y), and get a new n.
Point 8: segment's order does not matter.
CPPCPPPP reaches to the same number with CPPPPCPP.
Point 9: so then you will realize that the solution is like this. If
n's prime factorization is p^a * q^b * r^c where p q r are prime divisors of n, then the whole array is one permutation of the segment array: a number of segment-1 "CPP...P" with p-1 P, b number of segment-2 "CPP..P" with q-1 P, c number of segment-3 "CPP..P" with r-1P. So the whole solution is: a*p + b*q + c*r.
Point 10: the given solution in this discussion thread is always beginning from smallest prime divisor, which makes it look like a greedy solution, but that we know it's a greedy solution gives us little value, because the correctness proof lies in prime factoring.
https://discuss.leetcode.com/topic/97752/very-simple-java-solution-with-detail-explanation