# [LeetCode] 650. 2 Keys Keyboard 两键的键盘

2021年09月15日 阅读数：1

Initially on a notepad only one character 'A' is present. You can perform two operations on this notepad for each step:html

1. `Copy All`: You can copy all the characters present on the notepad (partial copy is not allowed).
2. `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'.java

Example 1:python

```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:数组

1. The `n` will be in the range [1, 1000].

Java:orm

```class 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];
}
}　　```

Python:htm

```class Solution(object):
def minSteps(self, n):
"""
:type n: int
:rtype: int
"""
result = 0
p = 2
# the answer is the sum of prime factors
while p**2 <= n:
while n % p == 0:
result += p
n //= p
p += 1
if n > 1:
result += n
return result　　```

C++:

```class Solution {
public:
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;
}
};
```

C++:

```class Solution {
public:
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];
}
};
```

C++:

```class Solution {
public:
int minSteps(int n) {
int res = 0;
for (int i = 2; i <= n; ++i) {
while (n % i == 0) {
res += i;
n /= i;
}
}
return res;
}
};
```

[LeetCode] 651. 4 Keys Keyboard 四键的键盘