Why do you need DP?


  • 0
    B

    There's a pattern associate with this problem, as you may observe:
    4 = 2 + 2
    5 = 2 + 3
    6 = 3 + 3
    7 = (3) + 2 + 2
    8 = (3) + 2 + 3
    9 = (3) + 3 + 3
    10 = (3 + 3) + 2 + 2
    11 = (3 + 3) + 2 + 3
    12 = (3 + 3) + 3 + 3
    13 = (3 + 3 + 3) + 2 + 2
    See? So I came up with a solution without using DP, I think it is O(logn) given that pow is O(logn). But since integer is 32-bit which is fixed, you may argue it is O(1).

    int integerBreak(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;
        
        int extraThrees = (n-4)/3;
        int index = (n-4)%3;
        return power(3, extraThrees) * (index==0?4:(index==1?6:9));
    }
    
    int power(int a, int n) {
        if (n == 0) return 1;
        if (n == 1) return a;
    
        int subres = power(a,n/2);
        if (n%2 == 1) return subres * subres * a;
        else return subres * subres;
    }

  • 0

    This is a typical math problem, lots of us have come up with this...of course DP is a choice if you cannot think of the solution in a instant.


Log in to reply
 

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