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


  • 1
    F

    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.


Log in to reply
 

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