LeetCode 343. Integer Break 剑指Offer 14. 剪绳子 [Medium]

发表于 更新于 阅读次数：

题目来源：https://leetcode.com/problems/integer-break/

题目难度：Medium

题目

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

Example 1:

1
2
3
Input: 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

1
2
3
Input: 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Note: You may assume that n is not less than 2 and not larger than 58.

解答1[Java]：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
    public int integerBreak(int n) {
        if (n == 2) {
            return 1;
        } else if (n == 3) {
            return 2;
        }

        int[] product = new int[n + 1];

        product[2] = 2;
        product[3] = 3;

        int maxProduct;

        for (int i = 4; i <= n; ++i) {
            maxProduct = 0;
            for (int j = 2; j <= i / 2; ++j) {
                int tempProduct = product[j] * product[i - j];
                if (tempProduct > maxProduct) {
                    maxProduct = tempProduct;
                }
            }
            product[i] = maxProduct;
        }

        return product[n];
    }
}

分析

长度为 2 和 3 的时候其实不切更好的，但是要求要切，可以当作特殊情况直接返回对应的结果。

动态规划的思路：

定义一个数组 product[]，但是注意，长度为 2 和 3 的时候，我们不再切分，所以我们使 product[2] 为 2，product[3] 为 3。然后从 4 开始计算每个数切分后的最大值。

解答2[Java]：贪心算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int integerBreak(int n) {
        if (n == 2) {
            return 1;
        } else if (n == 3) {
            return 2;
        }

        int remainder = n % 3;
        int result = n / 3;

        if (remainder == 0) {
            return (int) Math.pow(3, result);
        } else if (remainder == 1) {
            return (int) Math.pow(3, result - 1) * 4;
        } else {
            return (int) Math.pow(3, result) * 2;
        }
    }
}

分析

切要一下一下的切。对于一个数，切还是不切，要看切之后乘积是不是比原来更大。

使用 $N$ 表示一个数，使用函数 $f=x(N-x)$ 表示切分后的乘积。当 $x=\frac{N}{2}$ 时，乘积最大。

但是因为 $N$ 和 $x$ 都必须是整数，

那么当 $N$ 是偶数的时候，则当 $x=\frac{N}{2}$ 时乘积最大，最大为 $\frac{N}{2} \times \frac{N}{2}$。

当 $N$ 是偶数的时候，则当 $x=\frac{N+1}{2}$ 或者 $x=\frac{N-1}{2}$ 时，乘积最大，最大值为 $\frac{N+1}{2} \times \frac{N-1}{2}$

如果想要切分之后的乘积比原来更大，则要求 $\frac{N}{2} \times \frac{N}{2} > N$ 和 $\frac{N+1}{2} \times \frac{N-1}{2} > N$

当 $N$ 是偶数的时候，$N \ge 4$ 的时候，切分后乘积大于等于原来的数。

当 $N$ 是奇数的时候，$N \ge 5$ 的时候，切分后乘积更大。

也就是说，只要 $N \ge 4$ 的时候我们就要切分。2 和 3 的时候不切分。

4 的时候可以切分成 2 和 2，5 的时候可以切分成 2 和 3。

然后你会发现，所有的数最后都会被切分成若干个 2 和若干个 3。

所以现在问题就变成 $N = 2x + 3y$ 如果分配 $x$ 和 $y$ 的问题。

$3(N-3)$ 和 $2(N-2)$ 哪个大？

$3(N-3)-2(N-2)=N-5$

当 $N>5$ 时，优先切 3 的到的结果更大。

当 $N \le 5$ 时，也就只有 4 和 5 两种情况，4 的话切和不切是一样的乘积都不会变大，5 的话切 2 和切 3 是一样的，切完乘积都是 6。

参考资料

  1. A simple explanation of the math part and a O(n) solution - LeetCode Discussion