给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例 2:
输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
因为n可以拆分成两个数，也可以拆分多个数。 拆分成两个数的时候乘积就是i * (n - i)，也可以选择继续拆分：integerBreak(n - i)就是将n - i继续拆分的结果，但是我们并不知道种哪拆分的结果更大，所以我们要取二者的较大值作为当前拆分的最大值。
class Solution { int n; int ans; public int integerBreak(int n) { this.n=n; dfs(1,0,1); return ans; } void dfs(int start,int sum,int mult){ if(sum==n){ if(mult>ans) ans=mult; return ; } for(int i=start;i<=n-1;i++){ if(sum+i>n) break; dfs(i,sum+i,mult*i); } } }递归自顶向下容易超时，所以再加上一个备忘录。 这个备忘录可以是HashMap也可以是数组。
class Solution { HashMap<Integer,Integer> hash=new HashMap<>(); public int integerBreak(int n) { if(n==2) return 1; //如果有key值n，就直接返回value if(hash.containsKey(n)) return hash.get(n); //下面是没有key，就要计算，然后加入到hash中 int res=-1; for(int i=1;i<=n-2;i++){ res=Math.max(res,Math.max((n-i)*i,integerBreak(n-i)*i)); } hash.put(n,res); return res; } }因为memory需要分配内存，不可能再递归函数里面分配，所有要再加一个函数
class Solution { // 记忆化搜索-自顶向下 int[] memory; //因为memory需要分配内存，不可能再递归函数里面分配，所有要再加一个函数 public int integerBreak(int n) { memory = new int[n + 1]; return integerBreakHelper(n); } public int integerBreakHelper(int n) { if (n == 2) { return 1; } // memory的初始值为0，如果它不为0，说明已经计算过了，直接返回即可 if (memory[n] != 0) { return memory[n]; } int res = -1; for (int i = 1; i <= n - 2; i++) { res = Math.max(res, Math.max(i * integerBreakHelper(n - i), i * (n - i))); } // 将每次计算的结果保存到备忘录数组中 memory[n] = res; return res; } }动态规划
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++){ dp[i]=Math.max(dp[i],Math.max(j*(i-j) , j*dp[i-j])); } } return dp[n]; } }