DP. O(1) space. O(n) time complexity. Beat 95%.


  • -1
    C
    //f(n) = f(n-3) * 3 when n >= 7
    public int integerBreak(int n) {
        int [] ans = {0, 0, 1, 2, 4, 6, 9};
        if (n <= 6) return ans[n];
        int f1 = 4, f2 = 6, f3 = 9;
        for (int i = 7; i <= n; i++) {
            int tmp = f3;
            f3 = f1*3;
            f1 = f2;
            f2 = tmp;
        }
        return f3;
    }

Log in to reply
 

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