DP top-down + DP bottom-up + Magic solution
All solutions are accepted.\nWe need to ask the interview whether the result will exceed to limit of range of int32 or int64.\nIf not, we could use multiply ope
All solutions are accepted.\nWe need to ask the interview whether the result will exceed to limit of range of int32 or int64.\nIf not, we could use multiply operator simply.\n\npublic class Solution {\n    public int integerBreak(int n) {\n        return solve_magic(n);\n    }\n    \n    // accepted\n    private int solve_topdown(int n, int[] dp) {\n        if (n == 2) {\n            dp[2] = 1;\n            return dp[2];\n        }\n        \n        if (dp[n] > 0) {\n            return dp[n];\n        }\n        \n        for(int i = n - 1; i >=2; i--) {\n            // do not break\n            dp[n] = Math.max(dp[n], i * (n - i));\n            \n            // do break\n            dp[n] = Math.max(dp[n], solve_topdown(i, dp) * (n - i));\n        }\n        \n        return dp[n];\n    }\n    \n    // accepted\n    private int solve_bottomup(int n) {\n        int[] dp = new int[n + 1];\n        dp[2] = 1;\n        for(int i = 3; i <= n; i++) {\n           for(int j = 2; j <= i; j++) {\n               // do not break\n               dp[i] = Math.max(dp[i], j * (i - j));\n               \n               // do break\n               dp[i] = Math.max(dp[i], dp[j] * (i - j));\n           }\n        }\n        \n        return dp[n];\n    }\n\n    // accepted\n    private int solve_magic(int n) {\n        switch(n) {\n            case 2: return 1;\n            case 3: return 2;\n            case 4: return 4;\n            case 5: return 6;\n            case 6: return 9;\n            default: return solve_magic(n - 3) * 3;\n        }\n    }\n}
[]