# Java solutions from naive-DP to optimized-DP to non-DP

• This kind of problems bear the hallmarks of DP so I will explain in part `I` the naive DP solution first. Then in part `II`, I will introduce the optimized DP solution based on one interesting observation. Taking advantage of the same observation, the problem can actually be solved without any DP, as elaborated in part `III`. Lastly, a quick summary is given in part `IV` to share some thoughts about how to adapt the naive DP solution to the `4 Keys Keyboard` problem.

`I -- Naive DP`

As usual, for DP problems, we need to identify the optimal substructures for the original problem and relate its solution to its subproblems. To begin with, let's define `T(k)` as the minimum number of steps to get exactly `k` 'A' on the notepad. Then the original problem will be `T(n)` and we have the following termination conditions: `T(1) = 0`, since there is already one 'A' on the notepad initially. Now the key part is how to relate `T(k)` to its subproblems.

Apparently `T(k)` will depend on the sequence of operations performed to get `k` 'A' on the notepad. Now ask yourself these questions:

1. Can this sequence of operations end with `Copy All`? The answer is NO, because if this is the case, the last operation can always be removed without changing the number of 'A' on the notepad yet yielding a smaller number of steps.

2. Can this sequence of operations contain only ? The answer is again NO, because at the beginning there is no character being copied so pasting along won't change the number of 'A' on the notepad (a special case is when `n = 1`, but then we don't even need any operations).

So we conclude the sequence of operations must end with `Paste` with at least one `Copy All` in the middle. However, from the point of the last `Paste`, it only cares about characters which are copied last time, that is, the first `Copy All` operation from the end of the sequence. Assume the number of 'A' on the notepad is `i` when this `Copy All` operation is performed. Then how many more steps do we need to get `k` 'A' on the notepad by pasting only? The answer is `(k-i)/i`, where `k - i` is the remaining number of 'A' and `i` is the number of 'A' we can print on the notepad for each `Paste`. So the total number of steps from getting `i` 'A' to `k` 'A' is `k / i`, that is, one `Copy All` plus `(k-i)/i` `Paste`. Since we aim to minimize number of steps to get `k` 'A', we surely want to minimize the number of steps to `i` 'A', which by definition is `T(i)`, therefore the total number of steps getting `k` 'A' for this case is given by `T(i) + k/i`.

Since we don't really know when to perform the last `Copy All` operation, we can try each options and choose the one that produces the least number of steps. Here each option corresponds to a different value of `i` and if there are no additional restrictions, we have a total of `k - 1` such choices (`i` running from `1` to `k - 1`). Fortunately, we do require that the number of steps be integers, therefore `i` must be a divisor of `k`. In summary, we have:

`T(k) = min(T(i) + k/i)` where `1 <= i < k && k % i == 0`.

Here is the naive DP solution, with time complexity `O(n^2)` and space complexity `O(n)`.

``````public static int minSteps(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);

for (int k = 2; k <= n; k++) {
for (int i = 1; i < k; i++) {
if (k % i != 0) continue;
dp[k] = Math.min(dp[k], dp[i] + k / i);
}
}

return dp[n];
}
``````

`II -- Optimized DP`

It turns out that the inner loop in the naive DP solution can terminate early based on the following observation (unfortunately not so obvious): "In ascending order, let `k_1, k_2, ..., k_m` be the proper divisors of `k`, then we have `T(k_m) + k / k_m <= T(k_j) + k / k_j` for all `1 <= j < m`". The proof by mathematical induction is as follows (well, I was surprised that lots of you make use of this assumption without saying why).

First the statement is true for the simple case when `n = 2`. Next we assume it is valid for all cases with `n < k`, and will show it holds for `n = k`.

To smoothen the proof, it is useful to introduce the prime factorization of integers, which says any positive integer can be uniquely decomposed into product of prime numbers. For an integer `k`, let `[p_1, p_2, ..., p_t]` be the prime numbers in ascending order in its factorization and `[e_1, e_2, ..., e_t]` be the corresponding exponent array, then `k = p_1^e_1 * p_2^e_2 * ... * p_t^e_t`. Here we assume all the exponents are positive (i.e., prime factors of zero exponents are ignored).

Now if another integer `k'` is a divisor of `k`, then the prime factorization of `k'` has to satisfy the following two conditions:

1. The exponents of prime numbers other than `[p_1, p_2, ..., p_t]` must be zero.
2. Let `[e'_1, e'_2, ..., e'_t]` be the corresponding exponent array for `k'` in reference to `[p_1, p_2, ..., p_t]`, then `e'_j <= e_j` for all `1 <= j <= t` (Note that now `e'_j` is not necessarily positive but can be zero).

With the notations given above, we know `k`, `k_m` and `k_i` can be represented by three different exponent arrays, in reference to the same prime factors `[p_1, p_2, ..., p_t]`, since the latter two are proper divisors of the former. Assume again the exponent array for `k` is `[e_1, e_2, ..., e_t]`, then the exponent array for `k_m` will be `[e_1 - 1, e_2, ..., e_t]`, due to the fact that `k_m` is the largest proper divisor of `k`. Let `[e'_1, e'_2, ..., e'_t]` be the exponent array for `k_i`, we need to consider two cases: `k_m % k_i != 0` or `k_m % k_i == 0`.

For the former case, `k_i` is not a divisor of `k_m`. From our conclusion above, we must have `e'_1 > e_1 - 1 >= 0`, i.e., `e'_1` is positive. This is because `e'_j <= e_j` holds for all `2 <= j <= t` as `k_i` is a factor of `k`. If `e'_1 <= e'_1 - 1`, then `k_i` will also be a factor of `k_m`, contradicting with the condition that `k_m % k_i != 0`. Now let `d_i` be the largest proper factor of `k_i`, then the exponent array of `d_i` will be `[e'_1 - 1, e'_2, ..., e'_t]`. It is easy to show that `d_i` will also be a factor of `k_m`, since `e'_1 - 1 <= e_1 - 1`. Also we have the following equation `k * d_i = k_m * k_i`, which manifests itself in the notation of exponent arrays: `k * d_i = [e_1 + e'_1 - 1, e_2 + e'_2, ..., e_t + e'_t]` and `k_m * k_i = [e_1 - 1 + e'_1, e_2 + e'_2, ..., e_t + e'_t]`. Here comes the real proof for this case: `T(k_m) + k/k_m <= T(d_i) + k_m/d_i + k/k_m = T(d_i) + k/k_i + k_i/d_i = T(k_i) + k/k_i`. The first inequality comes from the induction assumption: `k_m < k` and `k_m % d_i == 0` implies `T(k_m) <= T(d_i) + k_m/d_i`. The following equality takes advantage of the equation `k * d_i = k_m * k_i` and finally the last equality uses the induction assumption again: `T(k_i) = T(d_i) + k_i/d_i`.

For the latter case, `k_i` is a proper divisor of `k_m`. Then by our induction assumption, `T(k_m) + k/k_m <= T(k_i) + k_m/k_i + k/k_m`. We only need to show that `k_m/k_i + k/k_m <= k/k_i`. Note that `k = k_m * p_1`, then `k/k_i = p_1 * k_m/k_i = p_1 + p_1 * (k_m/k_i - 1) >= p_1 + k_m/k_i = k/k_m + k_m/k_i`, where we have used the facts that `p_1 >= 2` and `k_m/k_i >= 2` to derive the inequality in the middle.

Thus we conclude the induction assumption is also true for the case `n = k`, hence validate our observation above.

Here is the optimized DP solution:

``````public int minSteps(int n) {
int[] dp = new int[n + 1];

for (int k = 2, i = 0; k <= n; k++) {
for (i = k >> 1; i >= 1 && k % i != 0; i--);
dp[k] = dp[i] + k / i;
}

return dp[n];
}
``````

`III -- Non-DP solution`

Our DP solution is based on the assumption that there is overlapping among subproblems. However, from the observation in part `II`, to solve `T(k)`, we only need `T(k_m)`, which in turn only requires knowledge of `T(k_m_m)`, `...`, where `k_m` is the largest proper divisor of `k_m`, and `k_m_m` is the largest proper divisor of `k_m`, and so on. Since the largest proper divisors are decreasing, there won't be any overlapping among the subproblems and the DP solution is an overkill here.

Here is the non-DP solution, which reduces the space complexity to O(1):

``````public int minSteps(int n) {
int res = 0;

for (int k = n, i = 0; k > 1; k = i) {
for (i = k >> 1; k % i != 0; i--);
res += k / i;
}

return res;
}
``````

If we look at the solution above more carefully, it is actually equivalent to adding up the prime factors of `n`, since the transformation sequence of the largest proper divisors will be (in the form of exponent array): `[e_1, e_2, ..., e_t] ==> [e_1 - 1, e_2, ..., e_t] ==> ... ==> [0, e_2, ..., e_t] ==> [0, e_2 - 1, ..., e_t] ==> ... ==> [0, 0, ..., 0]`. And for each such divisor, we add the corresponding prime factor to the resulting number of steps. Therefore the final answer will be `p_1 * e_1 + p_2 * e_2 + ... + p_t * e_t`. Here is the reformulated non-DP solution (more of a pure math solution):

``````public static int minSteps(int n) {
int res = 0;

for (int k = 2; k <= n; k++) {
for (; n % k == 0; res += k, n /= k);
}

return res;
}
``````

`IV -- Summary`

Although we have developed the non-DP solutions above, the ideas of the naive DP in part `I` carry merit as they can be adapted to solve the `4 Keys Keyboard` problem. The middle two operations `Ctrl-A` and `Ctrl-C` can be combined into one that resembles the `Copy All` operation here. Then again we can just try each position to perform the last `Ctrl-A` and `Ctrl-C` combo operation and choose the one that yields the most number of 'A' on the screen. A key difference between the two is that we need to press the keys twice to complete the combo operation. And interestingly enough, we also have observations similar in part `II`, which can reduce the time complexity down to `O(n)`. Anyway, hope this helps for solving the `2 Keys and 4 Keys Keyboard` problems.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.