Java 0ms DP Solution


  • 2
    J
    public int integerBreak(int n) {
        int[] res = new int[n+1];
        res[1] =1;
        // For numbers from 2 to 6
        for (int i = 2; i <= 6 && i <= n; i++){
            res[i] = (int)i/2 * ( i - (int)i/2);
        }
        // For numbers larger than 6, apply DP.
        for (int i = 7; i <= n; i++) {
            res[i] = Math.max(res[i-2] * 2, res[i-3] * 3);
        }
        return res[n];
    }

  • 0

    Nice solution. The first for loop actually works till 7


  • 0
    K

    @jguo11 What is the logic ? .. Why does the second loop work?


  • 0
    J

    @kireeti2 In order to get the maximum, we need to break the integer into as many 2 or 3 as we can. For example, for 15, the max comes from 3+3+3+3+3; for 16, it will be 3+3+3+3+2+2, etc.


  • 0
    K

    @jguo11 said in Java 0ms DP Solution:

    yes i got that ..but why would that work. any specific reason ..or just an observation?


  • 0
    J

    @kireeti2 For now, those are just my observation and there must be some math deductions can be done to prove it.


  • 1
    C

    @kireeti2 The key for this problem is that we need to break the number to 2s(or 4s), and 3s.
    First we need to know a fact that,if a,b > 3, |a-b| <= 1, then a*b>=a+b.

    So, if n = a + b, a = a1+a2, b=b1+b2, we should break n to a1+a2+b1+b2, |a1-a2|<1 and |b1-b2|<1 instead of a + b, because a1*a2>a, b1*b2>b. However, we shall stop when we get a 3 or 2, so what we shall do is to find the list of 3 and 2.

    You may have noticed why the 4 appeared. 'Cause if we break 4, we get 2+2, and 2+2 = 2*2, so it's the same with the condition that we get two 2s.


Log in to reply
 

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