Leetcode
Dynamic Programming
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 numbern. You have to getexactlyn'A' on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to getn'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.
    Thenwill 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)?