解法一：动态规划

当将 n 拆分成 n=a+b 时，可以计算 a*b 也可以继续对 b 进行拆分。由于 b<n ，可以直接使用已经保存过的低阶问题的结果，得到对 b 拆分可以得到的最大乘积。

  1. class Solution {
  2.     public int integerBreak(int n) {
  3.         // dp[i]表示i拆分得到的最大乘积
  4.         int[] dp = new int[n + 1];
  5.         dp[1] = 1;
  6.         for (int i = 2; i <= n; ++i) {
  7.             for (int j = 1; j < i; ++j) {
  8.                 // 拆成2个数, 或者对第二个数继续拆
  9.                 dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
  10.             }
  11.         }
  12.         return dp[n];
  13.     }
  14. }

解法二：优化的动态规划

官方题解的证明：https://leetcode-cn.com/problems/integer-break/solution/zheng-shu-chai-fen-by-leetcode-solution/

  1. class Solution {
  2.     public int integerBreak(int n) {
  3.         // dp[i]表示i拆分得到的最大乘积
  4.         int[] dp = new int[n + 1];
  5.         dp[2] = 1;
  6.         for (int i = 3; i <= n; ++i) {
  7.             dp[i] = Math.max(Math.max(2 * (i - 2), 2 * dp[i - 2]), Math.max(3 * (i - 3), 3 * dp[i - 3]));
  8.         }
  9.         return dp[n];
  10.     }
  11. }

解法三：数学方法

参考：https://leetcode-cn.com/problems/integer-break/solution/343-zheng-shu-chai-fen-tan-xin-by-jyd/

  1. class Solution {
  2.     public int integerBreak(int n) {
  3.         if (n <= 3) {
  4.             return n - 1;
  5.         }
  6.         // 商
  7.         int x = n / 3;
  8.         if (n % 3 == 0) {
  9.             return (int) (Math.pow(3, x));
  10.         } else if (n % 3 == 1) {
  11.             return (int) (Math.pow(3, x - 1) * 4);
  12.         } else {
  13.             return (int) (Math.pow(3, x) * 2);
  14.         }
  15.     }
  16. }