343. Integer Break.md

343. Integer Break

思路

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

思路一

这种有很多种拆分情况的题让人很容易想到动态规划，即数i的结果可以根据比i小的数的结果得出:

for j in [0, i):
   dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));

思路二

此题还有一些需要数学知识的解法，这里只说一个我想到的而且没在讨论区见过的，更多此题的数学解法可见讨论区

第一眼看到这个题目就感觉有高中数学题的影子:

若三个正数满足 x + y + z = 1, 求 xyz 的最大值。

答案就是三个数相等的时候。

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

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

思路二

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