Java DP solution


  • 48
    P
    public int integerBreak(int n) {
           int[] dp = new int[n + 1];
           dp[1] = 1;
           for(int i = 2; i <= n; i ++) {
               for(int j = 1; j < i; j ++) {
                   dp[i] = Math.max(dp[i], (Math.max(j,dp[j])) * (Math.max(i - j, dp[i - j])));
               }
           }
           return dp[n];
        }

  • 22
    G

    Got the same idea with you, and we can save half of the time by changing the inside loop

    j < i to 2*j <= i.

    public class Solution {

    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
       dp[1] = 1;
       for(int i = 2; i <= n; i ++) {
           for(int j = 1; 2*j <= i; j ++) {
               dp[i] = Math.max(dp[i], (Math.max(j,dp[j])) * (Math.max(i - j, dp[i - j])));
           }
       }
       return dp[n];
    }
    

    }


  • 1

    That's what I think


  • 11
    public int integerBreak(int n) {
        if(n > 3) n++;
        int[] dp = new int[n+1];
        dp[1] = 1;
        for(int i = 2; i <=n; i++) {
            for(int j = 1; j < i; j++) {
                dp[i] = Math.max(dp[i], j * dp[i-j]);
            }
        }
        return dp[n];
    }

  • 0
    This post is deleted!

  • 0
    R

    Can you please explain the thought of this algorithm?


  • 1
    S

    Though your solution is correct, its complexity is O(n2)


  • 4

    Same idea as yours. Here is another way to simplify DP function.

        public int integerBreak(int n) {
            // 1.Init except dp[n], since it cannot be itself and must break into two positive
            int[] maxProd = new int[n + 1];
            for (int i = 1; i < n; i++) {
                maxProd[i] = i;
            }
            
            // 2.Compute max product
            for (int i = 2; i <= n; i++) {
                for (int j = 1; j <= i - j; j++) { // Note: only check j <= i - j
                    maxProd[i] = Math.max(maxProd[i], maxProd[j] * maxProd[i - j]);
                }
            }
            return maxProd[n];
        }
    

  • 0
    W

    my 3ms c++ dp solution.
    The second loop can be half. since f(i)+f(n-i)==f(n-i)+f(i)

    int integerBreak(int n) {
        if(n==2) return 1;
        if(n==3) return 2;
        vector<int> cache(n+1, 0);
        cache[2] = 2;
        cache[3] = 3;
        for(int i=4; i<=n; i++){
            for(int j=2; j<=i>>1; j++){
                cache[i] = max(cache[i], cache[i-j]*cache[j]);
            }
        }
        return cache[n];
    }

  • 0

    @jaqenhgar looks like your solution is not pure dp like original post, still rely on the math. Normally j should be dp[j] to maximize value.


  • 1
    L

    @cdai Thanks for the idea. you can also compare i and dp[i] afterwards.

    public class Solution {
        public int integerBreak(int n) {
             int[] dp = new int[n + 1];
             for (int i = 2; i <= n; i++) {
                 dp[i - 1] = Math.max(i - 1, dp[i - 1]);
                 for (int j = 1; 2 * j <= i; j++) {
                     dp[i] = Math.max(dp[i], dp[j] * dp[i - j]);
                 }
             }
             return dp[n];
        }
    }
    

  • 0
    public int integerBreak(int n) {
    
    
        if(n == 0) return 0;
        if(n == 1 || n == 2) return 1;
    
        
        int[] opt = new int[n+1];
        opt[1] = 1;
        opt[2] = 1;
        opt[3] = 2;
        for(int i=1;i<n+1;i++){
            for(int j=2;j * 2 <= i;j++){ // j <= i/2, because when j >=i/2 they are dulplicated
                 //  no cut on the left part, optimal cut on the right part;
                 //  optimal cut on the left part, no cut on the right part;
                 //  optimal cut on the left part, optimal cut on the right part;
                 //  no cut on the left part, no cut on the right part;
                 // max of(j * opt[i-j]),(opt[j] * (i-j)),(opt[j]*opt[i-j]),(j*(i-j))
                int t = Math.max(j,opt[j]) * Math.max((i-j) , opt[i-j]);
                opt[i] = Math.max(opt[i], t);
            }
        }
    
        return opt[n];
    }

  • 0
    S

    Why can we assume dp[1] = 1?


  • 0

    Clearly the pure math solution is better, but the DP solution is a little easier to understand, IMO - C#

    public class Solution {
        public int IntegerBreak(int n) {
            int[] dp = new int[n+1];
            dp[1] = 1;
            for (int i = 1; i <= n; i++)
            {
                int max = 1;
                for (int j = 1; j < i; j++)
                {
                    int factor1 = Math.Max(j, dp[j]);
                    int factor2 = Math.Max(i-j, dp[i-j]);
                    max = Math.Max(max, factor1 * factor2);
                }
                dp[i] = max;
            }
            return dp[n];
        }
    

  • 0
    L

    thank you for your solution


  • 0
    S
    This post is deleted!

  • 0
    B

    @cdai awesome


  • 0
    C

    Can someone explain this line?

    Math.max(dp[i], (Math.max(j,dp[j])) * (Math.max(i - j, dp[i - j])));

    I don't get what is being computed there.


  • 0
    B

    @jaqenhgar said in Java DP solution:

    if(n > 3) n++;

    Could you please let us know the intuition behind this step?
    I coded the solution which is almost same as yours. The only statement I was missing was if(n > 3) n++;. I did notice that the values returned for n were at location n+1 in my dp table. So, did you just do n++ to return the correct values or is there some intuition behind this?


  • 0
    K

    @jaqenhgar said in Java DP solution:

    if(n > 3) n++

    why we will n++ here??


Log in to reply
 

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