IntegerBreak [source code]

public class IntegerBreak {
static
/******************************************************************************/
class Solution {
    int[] memo = new int[59];

    public int integerBreak(int n) {
        if (memo[n] > 0)
            return memo[n];
        int res = 0;
        for (int i = 1; i < n; i++) {
            res = Math.max(res, Math.max(i, integerBreak(i)) * (n - i));
        }
        memo[n] = res;
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        IntegerBreak.Solution tester = new IntegerBreak.Solution();
    }
}

这个题目看到N给了范围, 大概就知道submission肯定有无聊的hardcode解法了, 不过这个不是你需要关心的;

大概思考了一下, 很快就想到了这个问题的解法, 5分钟秒杀一个没见过的middle, 神奇. 最后的速度是1ms (44%), 应该是最优解了; 连两个hint都忘记看了;

这个首先是一个最值搜索的问题, 所以用DP并不过分; 这个题目的一个uncertainty就是, 我们到底最后这个最值, 需要把n分成几个数字; 那么这个就有点类似加法或者乘法的recursive理解了: 直接从2开始就行了, 然后每一个iteration+1;

另外根据hint, 这个题目是有一个math算法的; 不过无所谓了, DP算法其实应该也是O(N)的; //不对, 仔细想了一下, 这个算法的速度应该是N^2: fanning忘记考虑了;

这个是discussion最优解:

@lowiq said in Java O(n) DP solution, store and reuse products:

This is an O(n) solution, the idea is to store all previously calculated product, note any n>4 will guarantee to have a factor of 3. Modifed per suggestion of @jianbao.tao and @ericxliu, Thank you! 

public int integerBreak(int n) {  
    if (n <= 2) return 1;  
    if (n == 3) return 2;  
    if (n == 4) return 4;  
    int[] p = new int[n+1];  
    p[2] = 2;  
    p[3] = 3;  
    p[4] = 4;  
    for (int i = 5; i <= n; ++i) {  
        p[i] = 3 * p[i-3];  
    }  
    return p[n];  
}

Why the max product of any n>4 must contain a factor of 3?

  1. It can't contain any factor x that is >= 5, o.w., we can further increase the max product by decomposing x, as the decomposed x when x>=5 is strictly greater than x;
  2. Out of 1, 2, 3, 4, we know 1 won't be a factor of n when n>4, if n is an odd number, 3 must be there as a factor (2 and 4 can't add up to an odd number);
  3. Now say n is an even number (n>4) and only has factor of 2 and 4, we can always split a 6 to 3X3, which is better than 2X2X2.

    Therefore, the max product of any n (n>4) must contain a factor of 3. The recurrence relation holds.

Further, as it holds for all n (n>4), we will be only using 3 as factor for n (n>4), we keep subtracting 3 until n<=4, and adopt the remaining factor. This leads to the closed form answer: 

public int integerBreak(int n) {  
    if (n <= 2) return 1;  
    if (n == 3) return 2;  
    if (n % 3 == 0) return (int)Math.pow(3, (n/3));  
    else if (n % 3 == 1) return 4 * (int)Math.pow(3, (n-4)/3);  
    else return 2 * (int)Math.pow(3, (n-2)/3);  
}

As for the complexity of the close form solution, it depends on the implementation of the build-in pow, it could be O(logn) (as a simple O(logn) implementation exists), but not necessarily. The build-in pow could be better than that by using caching or bit level manipulation. I don’t know the answer though.

第一个解法还是很好理解的, 就是当前比如是n, 我们想想这个n是怎么来的? 可以理解为是从n-3的基础上, +3来的; 所以我们只要在n-3的基础上, 乘以这个+来的3, 就可以得到通过这条路径得到的最大product; 他的第二个代码其实是他自己本来的写法, 第一个代码好像是在这个代码的基础上改进得来的: 

public class Solution {  
    public int integerBreak(int n) {  
        if (n == 2) return 1;  
        if (n == 3) return 2;  
        int[] dp = new int[n + 1];  
        dp[2] = 2;  
        dp[3] = 3;  
        for (int i = 4; i <= n; i++) {  
            dp[i] = Math.max(3 * dp[i - 3], 2 * dp[i - 2]);  
        }  
        return dp[n];  
    }  
}

基本上也就是说, +3的方式得到n, 所得到的product是最大的; 比如你用+5, 那么其实不如用+2+3(贡献6>5); 比如你用+6, 不如+3+3(贡献9>6), 等等;

这个算法总体上来说是非常聪明的, 他的证明也算是比较完整的;

这个是另外一个解释, 解释的是上面这个人的第二个(较差的)版本的思路:

If we want to break a number, breaking it into 3s turns out to be the most efficient.
2^3 < 3^2
4^3 < 3^4
5^3 < 3^5
6^3 < 3^6
...

Therefore, intuitively, we want as many 3 as possible
if a number % 3 == 0, we just break it into 3s -> the product is Math.pow(3, n/3)

As for numbers % 3 == 1, we don't want the 'times 1' in the end;
borrowing a 3 is a natural thought.
if we borrow a 3, 3 can be divided into
case 1: 1 + 2 -> with the extra 1, we have 22 = 4
case 2: (0) + 3 -> with the extra 1, we have 4
turns out these two cases have the same results
so, for numbers % 3 == 1 -> the result would be Math.pow(3, n/3-1)*4

Then we have the numbers % 3 == 2 left
again, we try to borrow a 3,
case 1: 1+2 -> with the extra 2, we have 15 or 32 => 32 is better
case 2: 0+3 -> with the extra 2, we have 23 or 5 => 23 is better
and we actually just end up with not borrowing at all!
so we can just 2 if we have an extra 2 -> the result would be Math.pow(3, n/3)*2

Then, we have a couple corner cases two deal with since so far we only looked at
numbers that are larger than 3 -> luckily, we only have 2 and 3 left,
which are pretty easy to figure out

Thus my final solution is 

public class Solution {  
    public int integerBreak(int n) {  
        if(n <= 3) return n-1; //assuming n >= 2  
        return n%3 == 0 ? (int)Math.pow(3, n/3) : n%3 == 1 ? (int)Math.pow(3, n/3-1)*4 : (int)Math.pow(3, n/3)*2;  
    }  
}

这个解释还是非常详细的;

上面的证明有一点没有澄清: 为什么要尽可能多的3?

@ivtoskov said in Share some thought process about this problem:

Okay, I will try to provide an informal proof of why we want as many 3s as possible.

Firstly, it is easy to see why the result is n - 1 for n < 4. Therefore, we will only observe the case n >= 4.

The most optimal way to represent 4 is 2 * 2, again easy to see. What if n > 4?

We claim that 3 * (n - 3) > n for all n >= 5. This is indeed the case, since: 

3 * (n - 3) > n  
3n - 9 > n | -n  
2n - 9 > 0 | +9  
2n > 9 | /2  
n > 4.5 which is always true, since we assumed n >= 5.

With this proof we have actually shown that for any integer bigger than 4 it is actually better to decompose it as 3 times something instead of leaving it as it is.

Now we can recursively solve for x = n - 3. The new cases are: 

 1. x == 2 - in this case we leave it as it is, which means that n % 3 == 2.   
    This is covered by (int)Math.pow(3, n/3)*2 in his solution.  
 2. x == 3 - corresponds to n % 3 == 0, which is covered by (int)Math.pow(3, n/3)  
 3. x == 4 - corresponds to n % 3 == 1, which is covered by   
    (int)Math.pow(3, n/3-1)*4, meaning that we multiply by 4 instead of 3 once.  
 4. x >= 5 - in this case we can recursively solve for x.

A natural question would be why we chose exactly 3 and not any other number? It is indeed true that for any positive integer x >= 2 we have x * (n - x) >= n for n big enough. However, it wouldn't make sense to choose x >= 5, as we have already proved that it is better to decompose it using as many 3s as possible. So the only candidates left are x = 2 and x = 4: 

 1. x == 4 - We will have something like 4 * 4 * 4 ... * something. Let's take   
     only the first two factors: 4 * 4 < 3 * 3 * 2, so we can substitute all   
     of the fours with this expression, meaning that 3 is indeed the better   
     choice. For the remaining non-three factors, we can sum them up   
     and use the same recursion.  
 2. x == 2 - Similarly, 2 * 2 * 2 < 3 * 3.

The proof is not complete, but should be enough for you to understand the intuition.

这个解释还是非常给力的; 不过如果能够更深入的理解这个intuition, 就能直接想到最佳的(直接3 * dp[n-3])版本, 而不用做factor to
3这个中间步骤了;

不对, 看了一下其他人的分析, 他们认为这个用pow的版本事实上更快: 因为你只要做一个mod, 然后一个pow就行了, 而DP的解法至少还要O(N). 有一个人认为这个pow的解法是lgN. 但是有人认为JAVA本身采用的implementation实际上做的pow是O(1)的. 虽然说:

There is an O(log N) algorithm for integer exponentiation.

但是绝对不是O(N), 所以肯定是比那个DP解法要快的;

另外一个解释, 也解释的很好, 而且更加的学究:

@Chuqi said in A simple explanation of the math part and a O(n) solution:

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;  
    }  
}

这个是最高票的对pow方法的解释:

@lixx2100 said in Why factor 2 or 3? The math behind this problem.:

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.

解释的还算可以, 就是稍微有点复杂;

Stefan给出一个更简单的理解:

@StefanPochmann said in Why factor 2 or 3? The math behind this problem.:

You're making it pretty complicated.

If an optimal product contains a factor f >= 4, then you can replace it with factors 2 and f-2 without losing optimality, as 2*(f-2) = 2f-4 >= f. So you never need a factor greater than or equal to 4, meaning you only need factors 1, 2 and 3 (and 1 is of course wasteful and you'd only use it for n=2 and n=3, where it's needed).

For the rest I agree, 3*3 is simply better than 2*2*2, so you'd never use 2 more than twice.

有人在这个证明的基础上更进一步:

@lixx2100 said in Why factor 2 or 3? The math behind this problem.:

Yes, DP will guarantee the correctness for sure.

In fact, we can make a stronger statement, i.e., "the optimal solution will contain factors of 2 and/or 3 only, and the number of 2s will be no more than two."
The reason for that is simple, if we have more than two factor 2s, we can replace three of them by two factor 3s to increase the product, which is a contradiction.

This fact naturally suggests an O(log n) approach, which is also mentioned [here][1].

[1]: https://leetcode.com/discuss/98173/o-log-n-time-solution-with-explanation

这个人也认为我们对于这个问题的理解可以受益于从两个数字的情形的扩展:

@lixx2100 said in Why factor 2 or 3? The math behind this problem.:

Say we want to break n into x and y, where x and y are reals and x and y are positive. Then it is easy to see that xy reaches its maximum when x = y.
Therefore, if we have an uneven partition, making them even always produces larger product.

虽然不严谨, 但是是一个好的想法; 不对, 好像高中的时候证明过类似的东西? 这个定理好像三个数的时候也成立?

Problem Description

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.

For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

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

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Difficulty:Medium
Total Accepted:45.5K
Total Submissions:98.8K
Contributor: LeetCode
Related Topics
dynamic programming math

Hide Hint 1
There is a simple O(n) solution to this problem.
Hide Hint 2
You may check the breaking results of n ranging from 7 to 10 to discover the regularities.

results matching ""

    No results matching ""