A Java Solution


  • 0
    F
    // 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;
    			
    	}

Log in to reply
 

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