題目描述：
給定一個(gè)正整數(shù) n，將其拆分為至少兩個(gè)正整數(shù)的和，并使這些整數(shù)的乘積最大化。 返回你可以獲得的最大乘積。

說(shuō)明: 你可以假設(shè) n 不小于 2 且不大于 58

思路：
一般來(lái)說(shuō)，將一個(gè)數(shù)不斷除以2到1為止，得到的數(shù)字乘積是最大的。但是也有特例：比如8的最大值不是44=16，而是32*3=18。所以還是需要從2開(kāi)始遍歷到該數(shù)的一半進(jìn)行判斷。

狀態(tài)轉(zhuǎn)移方程為 dp[i] = Math.max(dp[i], dp[j] * dp[i-j]) (j from 2 to i/2)

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=2; j<=i/2; j++){
                dp[i] = Math.max(dp[i], dp[i-j]*dp[j]);
            }
        }
        return dp[n];
    }
}