Java DP Solution


  • 45
    L
        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];
        }
    

  • 25
    D

    @LinfinityLab Please take my knees, big god


  • 8
    B

    The value of j can start from i/2

    for (int j = i/2; j > 1; j--) {
                    if (i % j == 0) {
                        dp[i] = dp[j] + (i/j);
                        break;
                    }
                    
                }

  • 3
    X

    So easy to understand and I cannot figure it out in a half hour!
    DP is hard!


  • 4
    S

    @dongliang3571 your knees gain more reputation than the solution..lol


  • 0
    G

    I was thinking the i/j point, but end up think too much!


  • 3
    Y

    You don't even need dp[i] = i

        public int minSteps(int n) {
            int[] dp = new int[1001];
            for (int i = 2; i <= n; i++) {
                // sub-problem dp[i] := minSteps(i)
                for (int j = 2; j <= i; j++) {
                    // j := use j steps to create j copies
                    if (i % j == 0) {
                        dp[i] = j + dp[i / j];
                        break;
                    }
                }
            }
            return dp[n];
        }
    

  • 0
    R

    By far, I tested and found below solution is the fastest....

    public int minSteps(int n) {
        if(n<=5)return n<=1?0:n;
        int[] dp=new int[n+1];
        dp[0]=0;
        dp[1]=0;
        dp[2]=2;
        for(int i=3;i<dp.length;i++){
            dp[i]=i;
            for(int j=2;j<=Math.sqrt(i);j++){
                if(j*(i/j)==i){
                    dp[i]=Math.min(dp[i],dp[i/j]+j);
                    break;
                }
            }
        }
        return dp[n];
    }

  • 8
    Y

    @realhly88

    Pure loop solution is the fastest I found, only took 9 ms

        public int minSteps(int n) {
            int s = 0;
            for (int d = 2; d <= n; d++) {
                while (n % d == 0) {
                    s += d;
                    n /= d;
                }
            }
            return s;
        }
    

  • -2
    R

    @yuxiangmusic This way better!

    Please accept my knees....


  • 0
    H

    @yuxiangmusic This is far better than OP's solution. The recursive relation is about n's factors, so it doesn't make sense to memoize all the way from 1 to n.


  • -1
    C

    @LinfinityLab OP downvoted, @yuxiangmusic promoted.


  • 0
    R
    This post is deleted!

  • 5
    X

    Why can we break if dp[i] = dp[j] + (i/j);? Can smoeone give a prove?


  • 1
    S

    @xuanyue_vol The algorithm iterates through the factors backwards, selecting the greatest one first. This ensures that the amount of copy/paste operations is minimal. For instance, consider the number 8.

    You can do it in three ways:

    1. Copy (1A), paste (2A), paste (3A), paste (4A), paste (5A), paste (6A), paste (7A), paste (8A)
    2. Copy (1A), paste (2A), copy (2A), paste (4A), paste (6A), paste (8A)
    3. Copy (1A), paste (2A), paste (2A), copy (4A), paste (8A)

    Because 4 is 8's highest factor, it will give the optimal solution.


  • 0
    Z

    The logic is good, but the run time could be O(n^2). It should be TLE if test cases are proper.


  • 5
    X

    @shreydesai So this "iterates through the factors backwards, greatest one first. This ensures that the amount of copy/paste operations is minimal."

    This is where I'm not getting 100% confidence by a simple example.

    For an integer n and its largest factor k1 and a smaller factor k2, how can we guarantee (n/k1) + solve(n/k1) is guaranteed to be larger than (n/k2) + solve(n/k2)? could it be possible that n/k1 < n/k2 but solve(n/k1) > solve(n/k2)?


  • 0
    Z

    Could I ask what is the run time complexity, which is required in real interview?
    I got downvoted to claim it is O(n^2). Could someone provide a better analysis please?
    Btw, here is my O(n^0.5) solution. O(n^0.5) solution

    class Solution {
    public:
        int minSteps(int n) {
            int ans = 0;
            for (int i = 2; i <= sqrt(n); i++) {
                while (n%i == 0) {
                    ans += i;
                    n /= i;
                }
            }
            if (n > 1) ans += n;
            return ans;
        }
    };
    

  • 1
    G

    @shreydesai said in Java DP Solution:

    "Copy (1A), paste (2A), paste (2A), copy (4A), paste (8A)"

    This won't work, should be :
    Copy (1A), paste (2A), paste(3A)


  • 3
    G

    For dp[i] = dp[j] + i/j
    Example:
    dp[100] = dp[20] + 100/20 = 9 + 5 = 14
    = dp[25] + 100/25 = 10 + 4 = 14
    = dp[50] + 100/50 = 12 + 2 = 14

    That's why once we found one solution and break immediately.
    I'm kind of confused, why they all add up to the same number, whichever dividing factor I chose. Any mathematics behind?


Log in to reply
 

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