leetcode 343. 整数拆分 & leetcode 剑指 Offer 剑指 Offer 14- I. 剪绳子

343. 整数拆分

思路一：动态规划

一个整数被拆分成 k  和 (n-k)后，可以把(n-k)继续往下拆分，也可以选择不继续往下拆分，所以整数 n 被拆分后得到的乘积最大值就是 k*(n-k) 或者 k*(n-k被拆分后得到的乘积最大值)。由于每个正整数对应的最大乘积取决于比它小的正整数对应的最大乘积，因此可以使用动态规划求解。

令dp[i] 表示把正整数 i 拆分成至少两个整数后，这些正整数的最大乘积。特别地，0 不是正整数，1 是最小的正整数，0和 1 都不能拆分，因此dp[0]=dp[1]=0。

当i≥2 时，假设对正整数 ii 拆分出的第一个正整数是(1≤j<i），则有以下两种方案：

• 将 i 拆分成 j 和 i−j 的和，且i−j 不再拆分成多个正整数，此时的乘积是 j×(i−j)；
• 将 i 拆分成 j 和i−j 的和，且 i−j 继续拆分成多个正整数，此时的乘积是 j×dp[i−j]。

class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];

        for(int i = 2; i <= n; i++){
            int temp = 0;
            for(int j = 1; j < i; j++){
                temp = Math.max(temp, Math.max(j * (i - j), j * dp[i - j]));
            }
            dp[i] = temp;
        }
        return dp[n];
    }
}

执行用时：1 ms, 在所有 Java 提交中击败了62.23%的用户

内存消耗：34.8 MB, 在所有 Java 提交中击败了99.04%的用户

思路二：

思路参考：https://leetcode-cn.com/problems/integer-break/solution/343-zheng-shu-chai-fen-tan-xin-by-jyd/

根据数学证明，当一个数被拆分成尽可能多的3的时候，所有因子的乘积是最大的。所以我们应该尽可能把每段的长度控制为3， 看最多能拆成多少个3,但是如果n / 3不等于0， 代表该整数不能被3整除，这时需要特别判断一下：

如果余数为0， 最大乘积就是所有3的乘积

如果余数为1， 应该把其中一个3拿出来，配合这个1组成 2* 2， 因为2*2 = 4 > 3*1

如果余数为2， 结果就是所有3的乘积再乘以2

class Solution {
    public int integerBreak(int n) {
        if(n <= 3){
            return n - 1;
        }
        int a = n / 3;
        int b = n % 3;
        if(b == 0){
            return (int)Math.pow(3, a);
        }else if(b == 1){
            return (int)Math.pow(3, a - 1) * 4;
        }else{
            return (int)Math.pow(3, a) * 2;
        }
    }
}