美團(tuán)面試題(整數(shù)拆分)

來源：小浩算法

作者：程序員浩哥

這兩天越來越多的讀者私信小浩，說覺得只看題的話，不是很系統(tǒng)，想讓我系統(tǒng)的講一講各類數(shù)據(jù)結(jié)構(gòu)。對于這個問題，我統(tǒng)一回復(fù)一下，首先后面肯定是有系統(tǒng)的講解各類數(shù)據(jù)結(jié)構(gòu)的打算的，這個目前正在籌劃中，所以大家請放心！另外對于看題，如果擔(dān)心缺乏基礎(chǔ)知識看不懂的朋友們，大家請一萬個放心。老讀者都知道，我講題，一般都是會把這個題涉及到的基礎(chǔ)知識都給你過一遍的。當(dāng)然后面我也會用系列篇，把這些題目再串起來，所以大家還是耐心點(diǎn)的去看。記住，干就對了！

示例 1:

輸入: 2

輸出: 1

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

示例 2:

輸入: 10

輸出: 36

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

說明: 你可以假設(shè) n 不小于 2 且不大于 58。

（瞪一瞪就全部掌握）

這個題理解了題意的話，其實(shí)還是比較簡單的，一起看下。

要對一個整數(shù)進(jìn)行拆分，并且要使這些拆分完后的因子的乘積最大。我們可以先嘗試拆分幾個數(shù)值，測試一下。

通過觀察，首先肯定可以明確，2和3是沒辦法進(jìn)行拆分的最小因子。同時，我們好像能看出來：

• 只要把n盡可能的拆分成包含3的組合，就可以得到最大值。

• 如果沒辦法拆成3的組合，就退一步拆成2的組合。

• 對于3和2，沒辦法再進(jìn)行拆分。

根據(jù)分析，我們嘗試使用貪心進(jìn)行求解。因為一個數(shù)（假設(shè)為n）除以另一個數(shù)，總是包括整數(shù)部分（x）和余數(shù)部分（y）。那剛才也得到了，最優(yōu)因子是3，所以我們需要讓 n/3，這樣的話，余數(shù)可能是1,2 兩種可能性。

• 如果余數(shù)是1，剛才我們也分析過，對于1的拆分是沒有意義的，所以我們退一步，將最后一次的3和1的拆分，用2和2代替。

• 如果余數(shù)是2，那不消多說，直接乘以最后的2即可。

根據(jù)分析，得出代碼：

 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????//余數(shù)為1，退一步?3^(x-1)*2*2
 8????if?(y?==?1)?return?(int)?Math.pow(3,?x?-?1)?*?4;
 9????//余數(shù)為2，直接乘以2
10????return?(int)?Math.pow(3,?x)?*?2;
11}

鄭重申明（讀我的文章必看）：

• 本系列所有教程都不會用到復(fù)雜的語言特性，不需要擔(dān)心沒有學(xué)過相關(guān)語法，使用啥語言純屬本人翻牌子心情。

• 作為學(xué)術(shù)文章，雖然風(fēng)格可以風(fēng)趣，但嚴(yán)謹(jǐn)，我是認(rèn)真的。本文所有代碼均在leetcode上進(jìn)行過測試運(yùn)行。

• 算法思想才是最重要的。

答案是碰出來了，但是我們是通過觀察，發(fā)現(xiàn)最優(yōu)因子應(yīng)該是3。那如何來證明這個結(jié)論的正確性呢？

首先，通過均值不等式，很容易驗證當(dāng)每一個拆分值都相等的時候，才具有最大值，所以實(shí)際上就是將這個數(shù)均分。那么，對于整數(shù)，我們將其分解成份，每一份為則有

則相乘結(jié)果為：

求的極值點(diǎn)為，最接近的也就是3了。（注意：這里是整數(shù)，如果是實(shí)數(shù)，該證明則有漏洞）

一力破萬法，亂拳打死老師傅，使用萬能的動態(tài)規(guī)劃求解。

dp[i]代表i拆分之后得到的乘積的最大的元素，比如dp[4]就保存將4拆分后得到的最大的乘積。狀態(tài)轉(zhuǎn)移方程式為? ??

? ?

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

整體思路就是這樣，將一個大的問題，分解成一個一個的小問題，然后完成一個自底向上的過程。舉一個例子，比如計算10，可以拆分6和4，因為6的最大值3*3，以及4的最大值2*2都已經(jīng)得到，所以就替換成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?11????????????{
12????????????????dp[i]?=?max(dp[i],?max(dp[j],?j)?*?(i?-?j));
13????????????}
14????????}
15????????return(dp[n]);
16????}
17};

今天的題目可能有一定難度，建議大家自己寫寫畫畫，才能真正的做到理解和鞏固。

推薦閱讀

全部文章分類與整理（算法+數(shù)據(jù)結(jié)構(gòu)+計算機(jī)基礎(chǔ)），持續(xù)更新

【吐血整理】那些讓你起飛的計算機(jī)基礎(chǔ)知識：學(xué)什么，怎么學(xué)？

普普通通，我的三年大學(xué)

寫公眾號15個月以來，這一路上的學(xué)習(xí)與收獲

歷經(jīng)兩個月，我的秋招之路結(jié)束了！

2020 第一篇原創(chuàng) | 我是如何讓自己變的更加優(yōu)秀的？