class Solution {public int integerBreak(int n) {int[] dp = new int[n+1];dp[2] = 1;for(int i = 3; i<= n; i++){for(int j = 1; j<= i/2; j++){//j拆i，只需要遍历到 i/2 就可以，后面没有必要遍历dp[i] = Math.max(dp[i], Math.max(j*(i-j) , j*dp[i-j]));}// j * (i - j) 是单纯的把整数 i 拆分为两个数 }//而j * dp[i - j]是将 i 拆分成两个以及两个以上的个数return dp[n];}
}

确定dp数组以及下标的含义

        dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。

确定递推公式

         dp[i]最大乘积是怎么得到的呢？

        一个是j * (i - j) 直接相乘， 一个是j * dp[i - j]

dp数组初始化

        dp[2] = 1

复杂度分析

        时间复杂度：O(n^2)

        空间复杂度：O(n)