题目看这里 343. 整数拆分

动态规划

这道题目有个很巧妙的解法是利用数学规律，但是我先讨论这道题的常规解法：动态规划。

题目要求把一个正整数拆分为两个或两个以上的正整数的和，然后求这些拆分出来的正整数的乘积。因为每一个数都依赖它前面比它小的正整数的值，所以考虑用动态规划。
设dp[i]是构成数字 i 的正整数的乘积，那么dp[i]=max( max( i*(i-j), j*dp[i-j] ), dp[i])，因为这个递推公式在最内层循环，所以每一次取最大值的时候需要把dp[i]也考虑进。
因为0，1都不能拆分，所以初始化dp[0]和dp[1]都是0，因为在后面的循环中会计算到dp[j]，所以我没有使用dp[j]*dp[i-j]，

class Solution {
    public int integerBreak(int n) {
        if(n<=3)return n-1;
        int[] dp=new int[n+1];
        for(int i=2; i<=n; i++){
            for(int j=1; j<i; j++){
                dp[i]=Math.max(Math.max(j*(i-j), j*dp[i-j]), dp[i]);
            }
        }
        return dp[n];
    }
}

另一种动态规划在上面的动态规划基础上做了一些小改进，在内层循环里面判断的是j<=i-j，并且dp[i]=Math.max(dp[i], dp[j]*dp[i-j])，这是因为使用dp[i]=Math.max(dp[i], dp[j]*dp[i-j])来获得dp[i]的最大值，不需要遍历整个i范围内的j的值。

class Solution {
    public int integerBreak(int n) {
        if(n<=3)return n-1;
        int[] dp=new int[n+1];
        dp[1]=1;
        dp[2]=2;
        dp[3]=3;
        for(int i=4; i<=n; i++){
            for(int j=1; j<=i-j; j++){
                dp[i]=Math.max(dp[i],dp[j]*dp[i-j]);
            }
        }
        return dp[n];
    }
}

数学方法

数学方法首先要证明“把正整数n分成尽可能多的正整数x，这些正整数的乘积最大”，证明的结果是 当把n分成多个3的和，这些3的乘积最大。具体证明可以看力扣官方题解，这个解法比较冷门。