650 2 Keys Keyboard

# 1. Question

Initially on a notepad only one character 'A' is present. You can perform two operations on this notepad for each step:
1. 1.
`Copy All`: You can copy all the characters present on the notepad (partial copy is not allowed).
2. 2.
`Paste`: You can paste the characters which are copied last time.
Given a number`n`. You have to getexactly`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:
1
Input: 3
2
3
Output: 3
4
5
Explanation:
6
7
Intitally, we have one character 'A'.
8
In step 1, we use Copy All operation.
9
In step 2, we use Paste operation to get 'AA'.
10
In step 3, we use Paste operation to get 'AAA'.
Copied!
Note:
1. 1.
The`n`will be in the range [1, 1000].

# 2. Implementation

(1) DP
1
class Solution {
2
public int minSteps(int n) {
3
if (n <= 1) {
4
return 0;
5
}
6
int[] dp = new int[n + 1];
7
8
for (int i = 1; i <= n; i++) {
9
dp[i] = i;
10
for (int j = i - 1; j >= 1; j--) {
11
if (i % j == 0) {
12
dp[i] = Math.min(dp[i], dp[j] + i / j);
13
}
14
}
15
}
16
return dp[n];
17
}
18
}
Copied!

# 3. Time & Space Complexity

DFS + Memoization: 时间复杂度O(k ^(mn)), k是offer的数量, m是item的个数，n是每个item要买的个数，空间复杂度O(mn)?