LeetCode_116_IntegerBreak

1. question: 整数拆分（中等）

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/integer-break

示例 1:

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

示例 2:

输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

提示:

2 <= n <= 58

2. answers

这道题最开始没想出来，思路明显和爬楼梯以及不同路径不一样，这两道题是物理上的动态规划，即前一步都是实实在在存在的，即题目中指明了递推公式。而本道题，则是逻辑上的动态规划，题目中没有指明递推公式。

首先，题目要求是一个数，可拆分成至少两个数，并且其乘积最大。显然，最少是两个数，那么这两个数，一定是在自己的基础上是最优的，即这两个数，要么本身最大，要么是可以继续拆分成两个数，使得乘积最大。

我们知道，既然一个数可以拆分成两个子数（最优），那么这两个子数一定是小于本数的，而子数可以继续拆分，求解其最优的。继续下去，直到子数不能拆分为止。这就是递推公式。每个数N，它的最优解都是从[2, N]中的可能子数最优解中选取的，比如(1, n-1)，(2, n-2)，(3, n-3)，(4, n-4)等等，而我们只需要将1,2,3…n-1的最优解都计算出来即可，在计算的过程中，每个值都取决于前面的最优解，这就是递推公式，Max(n) = Max((1, n-1), (2, n-2), ...)。

所以，从2开始，到N，遍历每个数，计算其最优解。这样，后续的每个数，都可以使用前面的结果。代码如下所示：

public class Solution_0116_02 {

    public int integerBreak(int n) {

        // 保存每个数的最优值（最少分成两个数）
        // 初始化为0
        int[] result = new int[n + 1];

        // 注意，最小数为2，因为1不能拆成两个数
        result[2] = 1;

        // 遍历每个数，其最优值，即所有可能的加数乘积，即 i, 和 n-i，
        // 主要是比较 i * (n-i) 和 i * result[n-i]，也就是说判断对于加数，是否继续拆分。
        for (int i = 3; i <= n; i++) {

            // 对 数字 i 计算其最优值。
            // 注意，对于一个数，比如 10，分成 1 * 9 以及 9 * 1 是一样的，所以这里和数尽量不要重复。也就是说，尽量小于等于其1/2。
            for (int j = 1; j <= i / 2; j++) {

                // 这里，无论是j还是 i-j，都是小于i的。判断是否继续拆分。
                // 注意，这里是判断i的所有可能的情况，每次都取最大值
                result[i] = Math.max(result[i], Math.max(j * (i - j), j * result[ i- j]));
            }

        }

        return result[n];

    }

    public static void main(String[] args) {
        System.out.println();

        Solution_0116_02 s = new Solution_0116_02();

        System.out.println(s.integerBreak(10));
    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。