TwoKeysKeyboard [source code]
public class TwoKeysKeyboard {
static
/******************************************************************************/
class Solution {
public int minSteps(int n) {
if (n == 1)
return 0;
Set<Integer> set = new HashSet<> ();
Queue<int[]> queue = new LinkedList<> ();
queue.offer (new int[]{1, 1});
set.add (1001);
int res = 1;
while (!queue.isEmpty ()) {
int size = queue.size ();
for (int i = 0; i < size; i++) {
int[] state = queue.poll ();
int outputLen = state[0], clipLen = state[1];
if (outputLen == n)
return res;
int hash = outputLen * 1000 + outputLen;
if (!set.contains (hash)) {
queue.offer (new int[] {outputLen, outputLen});
set.add (hash);
}
hash = (outputLen + clipLen) * 1000 + clipLen;
if (!set.contains (hash) && outputLen + clipLen <= n) {
queue.offer (new int[] {outputLen + clipLen, clipLen});
set.add (hash);
}
}
// position of this increment very sensitive;
res++;
}
return -1;
}
}
/******************************************************************************/
public static void main(String[] args) {
TwoKeysKeyboard.Solution tester = new TwoKeysKeyboard.Solution();
int[] inputs = {
2, 2,
3, 3,
5, 5,
6, 5,
9, 6,
10, 7,
};
for (int i = 0; i < inputs.length / 2; i++) {
int n = inputs[2 * i], ans = inputs[2 * i + 1];
System.out.println (Printer.separator ());
int output = tester.minSteps (n);
System.out.printf ("%d -> %s, expected: %d\n",
n, Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
);
}
}
}
感觉上次的那个4key的问题其实我也没有完全搞懂, 这个题目做起来也很生疏, 最后写了这个算法, 但是是错的:
class Solution {
public int minSteps(int n) {
int[] dp = new int[Math.max (5, n) + 1];
dp[1] = 0;
dp[2] = 2;
dp[3] = 3;
dp[4] = 4;
dp[5] = 5;
if (n <= 3)
return dp[n];
for (int i = 6; i < n + 1; i++) {
int minMove = Integer.MAX_VALUE;
for (int j = 2 * (i + 2) / 3; j < i; j++) {
minMove = Math.min (dp[j - (i - j)] + 2, minMove);
}
if (i % 2 == 0)
minMove = Math.min (minMove, dp[i / 2] + 2);
dp[i] = minMove;
}
return dp[n];
}
}
不想浪费时间了, 感觉这题还是有点不得要领;
另外虽然这题没有做出来, 但是还是有一些经验教训的; DP问题除了之前总结的define table, define dimension, define entry, define subproblem structure的标准protocol之外, 还有一些在思维过程中的技巧;
sample paths
DP问题很多时候难的地方在于, 有太多可能的path, 没有错, 在DP问题当中通常你都能找到一个path的概念. path当中的每一个move对应你在每一个格子所做的decision; 我们最后的目标是得到一个针对move的heuristics, 那么一个方法就是分析多个sample paths.
比如说这题, 刚开始也是半天想不出来怎么定义一个有效的entry & subproblem的组合; 那么我们还是用一个笨办法笔算的思路, 我决定举几个例子; 看看比如对于n等于7, 你总共可以有哪几种sequence呢? 再分析这些sample sequence, 来总结, subproblem structure的关键到底是什么;
more base cases
DP填表的时候, 尤其是刚开始开发的时候, 很容易一不小心就在回头的时候出界了; 这个时候的一个方法就是在最开始的时候多填一些base case;
另外, 上面的错误算法其实还用到了一点计算ceiling的技巧, 当然, 你也可以直接用Math.ceil函数来做, 不过如果手动做, 你要知道类似(n + 1) / 2, (n + 2) / 3这样的技巧;
最后上面的代码是模仿最后一个discussion的BFS解法写出来的; 虽然看起来是一个很naive的算法, 但是实际上写的时候还是有点花时间的; 主要是我对这种穷搜其实也不是特别熟悉; 几个注意的地方;
operation and state
因为这里最后是找的一个a path/sequence of moves/operations, 所以最后在写的时候, 就要自己脑子里面有一个明确的定义, 你的state到底是跟一个move什么关系? 比如我这里定义的, 其实是每一个state记录的是operation之后的状态; 当然, 这个定义并没有说一定要用哪种, 但是脑子里要定下来, 这样写代码的时候才不会混乱;
move = edge
如果真的要画图debug, 那么还是学习NLP的时候学到的技巧, state对应的是dot, 然后每一个move对应的是edge;
最后的速度是87ms (4%).
一个小问题, discussion里面该解法原来的做法是自己定义了一个class来代表两个length, 我这里的做法是直接用一个array, 各有优劣;int[]虽然方便, 但是不方便debug: 如果自己定义一个class和对应的toString, 那么debug会方便很多, 尤其是这里有collection的时候;
editorial
Approach #1: Prime Factorization [Accepted]
Intuition
We can break our moves into groups of (copy, paste, ..., paste). Let C denote copying and P denote 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.
这里表达的比较含糊, 实际的意思是, 在相同的sum的情况下(相同长度的sequence/path, 相同数量的move),最后能够得到的A的数量变多了, 因为对于p和q两个而言, *p*q能够比*(p+q)贡献更多的factor;
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.
class Solution {
public int minSteps(int n) {
int ans = 0, d = 2;
while (n > 1) {
while (n % d == 0) {
ans += d;
n /= d;
}
d++;
}
return ans;
}
}
另外这里也是稍微见识了一个很naive的factorization的算法; 基本就是一个一个的枚举; 注意这里的时间复杂度是根号N, 不是N;
这个算法本身还是对应了我之前的枚举path的思路; 通过观察不同的path, 来分析得到规律, 尤其你看他非常明确的把类似CPPCPPPPCP这样的path都给写出来了; 只有这样写出来, 而不是在脑子里空想, 你才容易看到规律; 这个也是为什么一开始就鼓励笔算的原因;
另外这个题目总的来说要求的数学内容还是太多了, 不知道discussion有没有稍微正常一点的算法;
好像微软就是非常喜欢出这种总结, 找规律类型的题目;
discussion最优解:
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];
}
这个虽然没有明说, 其实也是看到类似editorial里面的那种分组的规律; 只不过editorial得解法直接就是通过数学分析得到一个最优解的情形, 这里好歹还有一点搜索的过程;
一个小优化:
@bloomer said in Java DP Solution:
The value of j can start from i/2
``` for (int j = i/2; j > 1; j--) {
if (i % j == 0) {
dp[i] = dp[j] + (i/j);
break;
}}
@alexander said in [C++] [Java] Clean Code with Explanation - 4 lines, No DP:
* 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;C++
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; } };Java
```java
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;
}
}
好像大部分这些做题的人对于copy/paste问题都相当熟悉, 也都知道自然的做一个`CP..P`的组合了?
另外, 这里其实是一个Top-Down的DP, 没有memo. 为什么?
@alexander said in [\[C\+\+\] \[Java\] Clean Code with Explanation \- 4 lines, No DP](https://discuss.leetcode.com/post/205817):
> @anooptoffy Everytime the number just go smaller monotonically, there is no duplicate sub problem, why would memorization save any time?
---
discussion另外一个有意思的解法;
@shawngao said in [Java solution, Memorized BFS](https://discuss.leetcode.com/post/204251):
> General idea is Memorized BFS. Some optimization to reduce status to be searched.
> 1. Use a class ```Stat``` to describe a status which contains two fields: ```currLen``` stands for the length of current ```A(s)```, ```clipLen``` stands for the length of ```A(s)``` in clipboard.
> 2. For each ```Stat```, there's two possible moves: ```Copy All``` and ```Paste```. But we can trim some of them using following methods.
> 3. If we see a ```Stat``` second time, no need to continue (by using a String HashSet);
> 4. If new length is greater than target length, no need to do ```Paste```.
>
```java
public class Solution {
class Stat {
int currLen;
int clipLen;
public Stat (int a, int b) {
currLen = a; clipLen = b;
}
}
public int minSteps(int n) {
if (n == 1) return 0;
int step = 1;
Queue<Stat> queue = new LinkedList<>();
queue.add(new Stat(1, 1));
Set<String> set = new HashSet<>();
set.add("1,1");
while (!queue.isEmpty()) {
step++;
int size = queue.size();
for (int i = 0; i < size; i++) {
Stat s = queue.poll();
// Copy All
if (!set.contains(s.currLen + "," + s.currLen)) {
queue.add(new Stat(s.currLen, s.currLen));
set.add(s.currLen + "," + s.currLen);
}
// Paste
if (s.currLen + s.clipLen == n) return step;
if (!set.contains((s.currLen + s.clipLen) + "," + s.clipLen) && s.currLen + s.clipLen < n) {
queue.add(new Stat(s.currLen + s.clipLen, s.clipLen));
set.add((s.currLen + s.clipLen) + "," + s.clipLen);
}
}
}
return -1;
}
}
相对慢一点, 不过好歹是AC了;
这个还是一个相对穷搜的办法, 不过为什么他这里知道选择BFS而不是DFS? 一个可能的原因可能是因为我们这里要搜的是一个path/sequence, 所以BFS这种progress on depth的顺序可能更有利一些;
另外, 他这里第三条的道理, 是一个pruning, 但是背后到底是什么原因? 暂时没有看懂; 不过我估计如果没有这个pruning, 他这个方法可能会超时;
submission最优解肯定都是数学解, 不看了;
Problem Description
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 n will be in the range [1, 1000].
Difficulty:Medium
Total Accepted:14.2K
Total Submissions:31.6K
Contributor:apoorv_vikram
Companies
microsoft
Related Topics
dynamic programming
Similar Questions
4 Keys Keyboard