package Classify.DP.Medium;
import org.junit.jupiter.api.Test;
/**
*
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].
*/
public class KeysKeyboard {
/**
* 这题的思路就是 dp 代表的就是当前的 A 的数量,然后我们优先考虑上一步复制过的情况，因为这样能够最快的填满 n 个 A ，但是使用这种情况要注意的就是
* 我们可能上部赋值我们最后收不了尾，所以必须有一个判断就是我们能用上一步的复制的内容填满剩下的 A ，也就是 n % dp[i - 1] == 0
* 里面的内容的意思就是我们使用了上一步的复制的内容那么我们的字符串就直接翻倍，而且我们进行了一次复制，那么我们 count 就得加2
* @param n
* @return
*/
public int minSteps(int n) {
if (n == 1) {
return 0;
}
int[] dp = new int[1000];
dp[0] = 1;
int paste = 1;
int i = 0;
int count = 1;
while (dp[i] <= n) {
++i;
if (n % dp[i - 1] == 0) {
paste = dp[i - 1];
dp[i] = dp[i - 1] * 2;
++count;
if (paste != 1) {
++count;
}
} else {
dp[i] = dp[i - 1] + paste;
++count;
}
if (dp[i] == n) {
return count;
}
}
return count;
}
@Test
public void fun() {
System.out.println(minSteps(10));
}
}