MENU

LeetCode343. Integer Break(动态规划)

2019 年 03 月 24 日 • 阅读: 2342 • LeetCode阅读设置

LeetCode343. Integer Break(动态规划)

  • Medium
  • Accepted:75,299
  • Submissions:158,763

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:

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

Example 2:

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.


链接

https://leetcode.com/problems/integer-break

题意

给定一个正整数n,将其分解为至少两个数的和,使得这些分解的数的乘积最大。

题解

一个暴力的思路是把n所有可能的分解都求出来,然后取乘积最大值。

假设我们用f(n)表示分解n得到的乘积最大值,那么f(n) = max{1*f(n-1), 2*f(n-2), 3*f(n-3), ... , (n-1)*f(1)},比如对于f(5):

注意这种分解方法并没有考虑到n = i * (n - i)的情况,即直接分解成两个数而不是对n - i再分解,需要手动加上。

我们可以采用递归的方法来解决这个问题,但是会包含很多重复的计算,所以可以使用记忆化搜索。当然也可以直接使用动态规划。

时间复杂度$O(n^2)​$。

代码

  • Runtime: 4 ms, faster than 100.00% of C++ online submissions for Integer Break.
  • Memory Usage: 8.5 MB, less than 19.32% of C++ online submissions for Integer Break.
class Solution {
private:
    vector <int> vis;
    int solve(int n)
    {
        if (n == 1)
            return 1;
        if (vis[n] != -1)
            return vis[n];
        int res = -1;
        for (int i = 1; i < n; ++i)
            res = max(max(res, i * (n - i)), i * solve(n - i));
        return vis[n] = res;
    }
public:
    int integerBreak(int n) {
        vis = vector<int>(n + 1, -1);
        return solve(n);
    }
};
class Solution {
public:
    int integerBreak(int n) {
        vector <int> ans(n + 1, 1);
        for (int i = 2; i <= n; ++i)
            for (int j = 1; j < i; ++j)
                ans[i] = max(max(ans[i], j * (i - j)), j * ans[i - j]);
        return ans[n];
    }
};

当然还有一种数学的办法解决这个问题,只考虑因子3,具体解释见文末。


The end.
2019年3月24日 星期日

参考

The first thing we should consider is : What is the max product if we break a number N into two factors?

I use a function to express this product: f=x(N-x)

When x=N/2, we get the maximum of this function.

However, factors should be integers. Thus the maximum is (N/2)(N/2) when N is even or (N-1)/2 (N+1)/2 when N is odd.

When the maximum of f is larger than N, we should do the break.

(N/2)*(N/2)>=N, then N>=4

(N-1)/2 *(N+1)/2>=N, then N>=5

These two expressions mean that factors should be less than 4, otherwise we can do the break and get a better product. The factors in last result should be 1, 2 or 3. Obviously, 1 should be abandoned. Thus, the factors of the perfect product should be 2 or 3.

The reason why we should use 3 as many as possible is

For 6, 3 3>2 2 * 2. Thus, the optimal product should contain no more than three 2.

Below is my accepted, O(N) solution.

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

I saw many solutions were referring to factors of 2 and 3. But why these two magic numbers? Why other factors do not work?
Let's study the math behind it.

For convenience, say n is sufficiently large and can be broken into any smaller real positive numbers. We now try to calculate which real number generates the largest product.
Assume we break n into (n / x) x's, then the product will be xn/x, and we want to maximize it.

Taking its derivative gives us n * xn/x-2 * (1 - ln(x)).
The derivative is positive when 0 < x < e, and equal to 0 when x = e, then becomes negative when x > e,
which indicates that the product increases as x increases, then reaches its maximum when x = e, then starts dropping.

This reveals the fact that if n is sufficiently large and we are allowed to break n into real numbers,
the best idea is to break it into nearly all e's.
On the other hand, if n is sufficiently large and we can only break n into integers, we should choose integers that are closer to e.
The only potential candidates are 2 and 3 since 2 < e < 3, but we will generally prefer 3 to 2. Why?

Of course, one can prove it based on the formula above, but there is a more natural way shown as follows.

6 = 2 + 2 + 2 = 3 + 3. But 2 * 2 * 2 < 3 * 3.
Therefore, if there are three 2's in the decomposition, we can replace them by two 3's to gain a larger product.

All the analysis above assumes n is significantly large. When n is small (say n <= 10), it may contain flaws.
For instance, when n = 4, we have 2 * 2 > 3 * 1.
To fix it, we keep breaking n into 3's until n gets smaller than 10, then solve the problem by brute-force.

最后编辑于: 2019 年 05 月 06 日