Leetcode - Integer Break

My code:

public class Solution {
    public int integerBreak(int n) {
        if (n <= 0) {
            return 0;
        }
        
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int begin = 1;
            int end = i - 1;
            int max = 0;
            while (begin <= end) {
                int n1 = dp[begin] * end;
                int n2 = dp[begin] * dp[end];
                int n3 = begin * end;
                int n4 = begin * dp[end];
                max = Math.max(max, Math.max(n1, Math.max(n2, Math.max(n3, n4))));
                begin++;
                end--;
            }

            dp[i] = max;
        }
        
        return dp[n];
    }
}

我的思想和 perfect square 这道题目很类似。
如果是 8
那么
1, 7
2, 6
3, 5
4, 4
可以组成他。
然后1,2,3,4,5,6,7
又可以再细分，
或者不分。
所以对于每个组合，可以有四种结果，拿出最大的就行。
比如，
3, 5
可以是
3 * 5
(1 * 2) * 5
3 * (2 * 3)
(1 * 2) * (2 * 3)

最大值是18
所以 dp[8] = 18

time complexity : O(n ^ 2)

然后答案说有一种O(n) 的解法：
https://discuss.leetcode.com/topic/55120/my-simple-dp-solution-o-n

看了下，就是找规律。没什么意思。。。
然后据说还有 O(log n) 的解法，也是玩数学游戏。不是很有意思。就不研究了.

Anyway, Good luck, Richardo! -- 08/27/2016