### 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.