class Solution { public int integerBreak(int n) { int[] dp = new int[n + 1]; //dp[2]对应的值应该是1，而dp[2]之前的元素在此题目中无现实意义，因此无需初始化 dp[2] = 1; for(int i = 3; i <= n; i++){ for(int j = 1; j <= i - j; j++){ dp = Math.max(dp, Math.max(dp[i - j] * j, j * (i - j))); } } return dp[n]; }}时间复杂度 O(n^2)
题外话
这道题用动态规划的话时间复杂度好像有点高，实在这道题可以用数学方法来写的，这里用到一个结论：当整数 n 尽大概地平分为 3时乘积最大。假如感爱好的同砚可以去证实一下。
class Solution { public int integerBreak(int n) { if(n <= 3) return n - 1; int a = n / 3, b = n % 3; //当 n 分刚好能分成多少个 3 时 if(b == 0) return (int)Math.pow(3, a); //当 n 尽大概分成 3 时，余出一个 1 if(b == 1) return (int)Math.pow(3, a - 1) * 4; //当 n 尽大概分成 3 时，余出一个 2 return (int)Math.pow(3, a) * 2; }}时间复杂度：O(1)
