A Java Solution

• ``````// if n == 2, then the answer will be 1 * 1
// if n == 3, then the answer will be 1 * 2
// if n >= 4, then
// since there are only finite number of ways to split n, so the optimal solution exists.
// Pick any one that can generate the optimal solution, let's call it OPT. First, let me prove that each number in this OPT will be less than or equal to 4 (if there is some x > 4 in OPT, then we can split x, and get 2 and (x-2) which will generate a better result, so in fact, no such x exists)
// Now, if 4 exists in OPT, we just split all the 4 into 2 and 2. Let's call it OPT'
// After that, only 1, 2, 3 can exist in OPT'.
// Now, I will show that 1 will not appear in OPT'
// Since 1+1 > 1*1, 1+2>1*2, 1+3>1*3, so 1 will not appear in OPT'
// Now, let me prove that  count(2) in OPT' will be less than 3.
// Since 2 * 2 * 2 < 3 * 3, that is to say, if you see  three 2 in OPT', then we can replace them by two 3(Thus OPT' is not an optimal solution)
// So count(2) in OPT' must be 0 or 1 or 2
// so if n % 3 == 0, count(2) must be 0 in OPT'
// if n % 3 == 1, count(2) must be 2 in OPT'
// if n % 3 == 2, count(2) must be 1 in OPT'

// if n >= 4, then
// 因为拆分方式有限, 所以最优解一定存在
// 任取一种最优拆分方式, 证明其中的各个数字都不会大于4(反证法: 如果其中有某个 a > 4, 则将a拆分为 2 * a - 2, 会得到更优解, 矛盾)
// 现在统一处理这个最优拆分方式: 如果其中有4, 则将所有 4 拆分为 2 * 2
// 统一处理后, 最优拆分中将只有 1, 2, 3(可能不都出现)
// 现在证明其实不会有1
// 因为 1+1 > 1*1, 1+2>1*2, 1+3>1*3, 所以其实不会有1存在
// 那么最优拆分中其实只会有 2, 3(可能不都出现)
// 现在证明 2 的个数一定不超过 3 个,
// 否则 2 * 2 * 2 < 3 * 3, 也就是说 3 个 2 不如 2 个 3 好, 所以2的个数只能是0,1,2
// 所以若 n % 3 == 0, 则标准化后的最优拆分中一定没有2
// 若 n % 3 == 1, 则标准化后的最优拆分中一定恰有2个2
// 若 n % 3 == 2, 则标准化后的最优拆分中一定恰有1个2

public int integerBreak(int n) {
if (n <= 3)
return n - 1;

int k = n / 3;
int ret = 1;

for (int i = 0;i < k;i++)
ret *= 3;

if (n % 3 == 0)
return ret;
if (n % 3 == 1)
return ret / 3 * 4;
return ret * 2;

}``````

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