LeetCode343-整数拆分

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/integer-break/

中文链接：https://leetcode-cn.com/problems/integer-break/

题目详述

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

示例 1:

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

示例 2:

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

说明: 你可以假设 n 不小于 2 且不大于 58。

题目详解

动态规划。注意子数组中元素是相邻的。

  • dp[i] 表示 i 分解后的最大乘积。
  • 则 dp[i + j] = Math.max(dp[i + j], Math.max(i, dp[i]) * Math.max(j, dp[j]));。
1
2
3
4
5
6
7
8
9
10
11
12
13
public class LeetCode_00343 {

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

实际上，这是一个数学问题。只有数字 2 和 3 分解成几个数的乘积后会变小，4 分解后不变，大于 4 的数分解后都会变大，所以要得到最大乘积需要一直分解，直到分解到不大于 4。并且在分解过程中，按 3 分解的结果大于按 2 分解的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class LeetCode_00343 {

    public int integerBreak(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;
        int res = 1;
        while (n > 4) {
            res *= 3;
            n -= 3;
        }
        res *= n;
        return res;
    }
}