343.整数拆分.md

343.整数拆分

题目

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

方法（动态规划）

每一个整数n拆分得到的最大乘积可以由比n小的整数拆分得到的最大乘积来得到，因此可以考虑用动态规划。

若要求i拆分得到的最大乘积，我们可以将i拆分为j和i - j之和，这时我们有两个选择：

• j不再继续拆分，这时乘积为j * (i - j)
• j继续向下拆分，因为j拆分得到的最大乘积为dp[j]，因此这时的乘积为dp[j] * (i - j)

将这两种情况的乘积取较大的那个，即为拆分i所能得到的最大乘积。

动态规划步骤：

• 定义dp[i]为将整数i拆分所能得到的最大乘积
• Base Case：dp[0] = 0, dp[1] = 1
• 状态转移方程：$\operatorname{dp}[i]=\max _{1 \leq j<i}{\max (j \times(i-j), j \times \operatorname{dp}[i-j])}$

代码

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