# 343. Integer Break 整数拆分

@TOC

## # 题目描述

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.

## # 解题方法

### # 数学解法

....

⇒ log(target) = x * log2 + ((N - 2 * x) / 3) * log3 ⇒ x * log2 + (N/3) * log3 - (2x/3) * log3 ⇒ (log2 - 2/3 * log3) * x + N/3 * log3 ⇒ -0.017 * x + N/3 * log3

python代码如下：

``````class Solution:
def integerBreak(self, n):
"""
:type n: int
:rtype: int
"""
if n == 2: return 1
if n == 3: return 2
res = 1
while n > 4:
res *= 3
n -= 3
return res * n
``````

C++代码如下：

``````class Solution {
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;
}
return res * n;
}
};
``````

### # 动态规划

``````class Solution(object):
def integerBreak(self, n):
"""
:type n: int
:rtype: int
"""
dp = [0, 0, 1, 2, 4, 6, 9]
for i in range(7, n + 1):
dp.append(dp[i - 3] * 3)
return dp[n]
``````

## # 日期

2018 年 5 月 28 日 —— 太阳真的像日光灯～ 2019 年 1 月 24 日 —— 快要回家了