题目描述

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

---

解题思路:

1. dp[i]定义:将正整数 i拆分成至少两个正整数的和之后，这些正整数的最大乘积
2. 令 k 是拆分出的第一个正整数，则剩下的部分是n−k，n−k可以不继续拆分，或者继续拆分成至少两个正整数的和。由于每个正整数对应的最大乘积取决于比它小的正整数对应的最大乘积，因此可以使用动态规划求解。
3. dp[i] =max(j * dp[i - j], j * (i - j);

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

---

踩坑记录:

1. 外层for循环控制整个正整数自底向上求解,内层for循环对当前要求解的值进行拆分
2. 拆分时从1开始

Q.E.D.