题目

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

示例 1:

输入: n = 2

输出: 1

解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: n = 10

输出: 36

解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

示例 3:

输入：m = 7, n = 3

输出：28

约束条件：

2 <= n <= 58

思路：

分析：动规五部曲。

1.确定dp[i]含义：拆分i，可以得到最大乘积为dp[i]

2 .确定递推公式： 最大乘积是怎么得到的，可以从1遍历到j，然后有两种渠道得到dp[i],一个是j*(ij)，一个是jdp[i-j]，相当于拆分了（i-j），为什么不拆分j呢？因为j是从1开始遍历的，遍历j的过程中，已经计算过拆分j的情况，如果都拆分的话，其实也是默认把所给的数强制拆分成了四份。所以递推公式是：dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});同时不断取最大值，满足dp[i]是最大

3.初始化dp数组。拆分0和1的最大乘积是多少？这个问题没什么解，所以从2开始初始化，dp[2] =1;

4.确定遍历顺序。 通过递推公式，可以看出dp[i]依赖的是dp[i-j]的状态，所以遍历i是从前往后的顺序，先有dp[i-j]再有dp[i];

代码实现：

class Solution {
    public int integerBreak(int n) {
        int[]dp = new int[n+1];
        dp[2] = 1;
        dp[3] = 2;
        dp[4] = 4;
        for(int i =3;i<=n;i++){
            for(int j =1;j<i-1;j++){
                dp[i] = Math.max(dp[i],Math.max(dp[i-j]*j,j*(i-j)));
            }
        }
        return dp[n];
    }
}