动态规划：整数拆分

class Solution {
     public int integerBreak(int n) {
        int []dp=new int[n+1];
        dp[2]=1; //dp[0]和dp[1]无意义，初始化dp2为1，因为递推公式与前面的有关，所以从前往后遍历
        for (int i = 3; i <=n; i++) { 
            for (int j = 1; j <=i/2 ; j++) {
                dp[i]=Math.max(dp[i],Math.max(dp[i-j]*j,j*(i-j)));  //dp[i]表示从i为3开始到最后查找的最大，第三项表示只拆分一次，第二项表示可以拆分多次
            }
        }

        return dp[n];
    }
}