LeetCode/solutions/343. Integer Break.md

# [343. Integer Break](https://leetcode.com/problems/integer-break/)

# 思路
把数n拆成多个数字的和，求这些数字的乘积的最大值。

## 思路一
这种有很多种拆分情况的题让人很容易想到动态规划，即数i的结果可以根据比i小的数的结果得出:
```
for j in [0, i):
   dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
```

## 思路二
此题还有一些需要数学知识的解法，这里只说一个我想到的而且没在讨论区见过的，更多此题的数学解法可见[讨论区](https://leetcode.com/problems/integer-break/discuss)

第一眼看到这个题目就感觉有高中数学题的影子:
```
若三个正数满足 x + y + z = 1, 求 xyz 的最大值。
```
答案就是三个数相等的时候。

所以我们可以把数n尽可能等分成2、3、4...份，然后计算这些情况中的最大乘积就可以了。
如何尽可能等分呢，如果想把n尽可能分成i份，则有`residue` 个等于`quotient + 1`, 其余等于`quotient`，其中`quotient = n / i; residue = n % i;`

# C++
## 思路一
``` C++
class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1, 1);
        for (int i = 3; i <= n; ++i) {
            for (int j = 1; j < i; ++j) {
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
};
```

## 思路二
``` C++
class Solution {
public:
    int integerBreak(int n) {
        int res = 0, quotient, residue;
        bool flag = true;
        for(int i = 2; i <= n; i++){
            quotient = n / i;
            residue = n % i;
            
            // i个数中, 有residue个等于 quotient + 1, 其余等于quotient
            int cur = pow(quotient + 1, residue) * pow(quotient, i - residue);            
            if(cur > res) res = cur;
            // else break; // 这里可以其实提前跳出
        }
        return res;
    }
};
```