漫画：美团面试题（整数拆分）

刺骨的言语ヽ痛彻心扉 2023-07-15 13:05 7阅读 0赞

点击上方蓝字设为星标![format_png][]

下面开始今天的学习～

![format_png 1][]

作者 | 程序员浩哥

来源 | 小浩算法

PART

整数拆分

343题：给定一个正整数 *n*，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。

示例 1:

输入: 2

输出: 1

解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: 10

输出: 36

解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

说明: 你可以假设 n 不小于 2 且不大于 58。

![瞪眼.gif][.gif]

（瞪一瞪就全部掌握）

PART

题目分析

![38.png][]

这个题理解了题意的话，其实还是比较简单的，一起看下。

要对一个整数进行拆分，并且要使这些拆分完后的因子的乘积最大。我们可以先尝试拆分几个数值，测试一下。

![format_png 2][]

通过观察，首先肯定可以明确，**2和3是没办法进行拆分的最小因子**。同时，我们好像能看出来：

*  只要把n尽可能的拆分成包含3的组合，就可以得到最大值。
 *  如果没办法拆成3的组合，就退一步拆成2的组合。
 *  对于3和2，没办法再进行拆分。

根据分析，我们尝试使用**贪心**进行求解。因为一个数（假设为n）除以另一个数，总是包括整数部分（x）和余数部分（y）。那刚才也得到了，**最优因子是3**，所以我们需要让 n/3，这样的话，余数可能是1,2 两种可能性。

*  如果余数是1，刚才我们也分析过，对于1的拆分是没有意义的，所以我们退一步，将最后一次的3和1的拆分，用2和2代替。
 *  如果余数是2，那不消多说，直接乘以最后的2即可。

根据分析，得出代码：

1//JAVA
     2public static int integerBreak(int n) {
     3    if (n <= 3) return n - 1;
     4    int x = n / 3, y = n % 3;
     5    //恰好整除，直接为3^x
     6    if (y == 0) return (int) Math.pow(3, x);
     7    //余数为1，退一步 3^(x-1)*2*2
     8    if (y == 1) return (int) Math.pow(3, x - 1) * 4;
     9    //余数为2，直接乘以2
    10    return (int) Math.pow(3, x) * 2;
    11}

![format_png 3][]

郑重申明（读我的文章必看）：

*  本系列所有教程都不会用到复杂的语言特性，不需要担心没有学过相关语法，使用啥语言纯属本人翻牌子心情。
 *  作为学术文章，虽然风格可以风趣，但严谨，我是认真的。本文所有代码均在leetcode上进行过测试运行。
 *  算法思想才是最重要的。

PART

证明过程

![38.png][]

答案是碰出来了，但是我们是通过观察，发现最优因子应该是3。那如何来证明这个结论的正确性呢？

首先，通过均值不等式，很容易验证当每一个拆分值都相等的时候，才具有最大值，所以实际上就是将这个数均分。那么，对于整数![format_png 4][]，我们将其分解成![format_png 5][]份，每一份为![format_png 6][]则有

![format_png 7][]  
则相乘结果为：  
![format_png 8][]

求![format_png 9][]的极值点为![format_png 10][]，最接近的也就是3了。（注意：这里是整数，如果是实数，该证明则有漏洞）

PART

都看不懂

![38.png][]

一力破万法，乱拳打死老师傅，使用万能的动态规划求解。

dp\[i\]代表i拆分之后得到的乘积的最大的元素，比如dp\[4\]就保存将4拆分后得到的最大的乘积。状态转移方程式为

dp\[i\]=max(dp\[i\],(i-j)\*max(dp\[j\],j))

整体思路就是这样，将一个大的问题，分解成一个一个的小问题，然后完成一个**自底向上**的过程。举一个例子，比如计算10，可以拆分6和4，因为6的最大值3\*3，以及4的最大值2\*2都已经得到，所以就替换成9和4，也就是10=3\*3\*4。

代码如下：（CPP听说很受欢迎？）

1//C++
     2class Solution {
     3public:
     4    int integerBreak(int n)
     5    {
     6        vector<int> dp(n + 1, 0);
     7        dp[1] = 1;
     8        for (int i = 2; i <= n; i++)
     9        {
    10            for (int j = 1; j < i; j++)
    11            {
    12                dp[i] = max(dp[i], max(dp[j], j) * (i - j));
    13            }
    14        }
    15        return(dp[n]);
    16    }
    17};

今天的题目可能有一定难度，建议大家自己写写画画，才能真正的做到理解和巩固。

推荐阅读：
    五分钟学算法：动手写一个双向链表
    
    当初我要是这么学习「进程和线程」就好了（附带思维导图）
    
    当初我要是这么学习操作系统就好了（附带思维导图）
    
    啥是布隆过滤器算法？

[format_png]: /images/20230528/9137995efe284e99b16164a86cf5d751.png
[format_png 1]: /images/20230528/d279b0a290424044be6113a661afd435.png
[.gif]: /images/20230528/874660bc59b842e1a298b67cea91ceb0.png
[38.png]: /images/20230528/a6766c45ef4a43faa47e965160642ccf.png
[format_png 2]: /images/20230528/3a892c67e37140a2a141c7830ddcdbf5.png
[format_png 3]: /images/20230528/748644971da34c0a8bdb7051cdb56259.png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3N2Zy9MVHB3Zkg4MnJpY2tBbzNlT1ZCNllqOWhzbWdRTUFleFU2dVFlZ0lqVmJXaWJiUm5ad3FpYlNzcWxudTRDdUZpY1VPaWNlYm9KSUhOSmtOY1p5VGF0WHlIUXdNMFU2VEQ4RlJ4OC82NDA?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3N2Zy9MVHB3Zkg4MnJpY2tBbzNlT1ZCNllqOWhzbWdRTUFleFVMUm9hcFdZYU9VRHBsTlM0WHlzcmhwcFd6SmFFWVBHRmljb2liRGZ6WFhJaHF4UzhUUWczNGMwMjZDeWdpYlQ1SEo3LzY0MA?x-oss-process=image/format,png
[format_png 6]: /images/20230528/342f4273539b4576831b9cf0fd7955e0.png
[format_png 7]: /images/20230528/a47707e8845b432e89c45ba17371ccc2.png
[format_png 8]: /images/20230528/1872fcb0afbe4814b626f389f58883ca.png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3N2Zy9MVHB3Zkg4MnJpY2tBbzNlT1ZCNllqOWhzbWdRTUFleFVZckxwTEpnOEp4a2pNaWNhTlIwMWNWb2lhU2RlZUx4VTltTkdQaGpHdGxDaWNBTU9USjlpY2J2QngzUFhpY1Z3RklkVXgvNjQw?x-oss-process=image/format,png
[format_png 10]: /images/20230528/2a507e61b8754474b2f7995b81abebef.png