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
