天天看點

LeetCode343之整數拆分(相關話題:數學柯西不等式,求導)

給定一個正整數 n,将其拆分為至少兩個正整數的和,并使這些整數的乘積最大化。 傳回你可以獲得的最大乘積。

示例 1:

輸入: 2

輸出: 1

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

示例 2:

輸入: 10

輸出: 36

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

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

設将整數 n 拆分為 a 個小數字:

n=n1​+n2​+...+na​

本題等價于求解:

max(n1​×n2​×...×na​)

以下數學推導總體分為兩步:① 當所有拆分出的數字相等時,乘積最大。② 最優拆分數字為 3 。

數學推導:

以下公式為“算術幾何均值不等式” ,等号當且僅當 n_1 = n_2 = ... = n_an1​=n2​=...=na​ 時成立。

LeetCode343之整數拆分(相關話題:數學柯西不等式,求導)
 推論一: 若拆分的數量 a 确定, 則 各拆分數字相等時 ,乘積最大。
LeetCode343之整數拆分(相關話題:數學柯西不等式,求導)
 推論二: 将數字 nn 盡可能以因子 33 等分時,乘積最大。

拆分規則:

最優: 3 。把數字 n 可能拆為多個因子 3 ,餘數可能為 0,1,2 三種情況。

次優: 2 。若餘數為 2 ;則保留,不再拆為 1+1

最差: 1 。若餘數為 1 ;則應把一份 3 + 1替換為 2 + 2,因為 2 * 2 > 3 *1

1.基本初等函數求導公式 

LeetCode343之整數拆分(相關話題:數學柯西不等式,求導)

  ​​​​​2.函數的和、差、積、商的求導法則

LeetCode343之整數拆分(相關話題:數學柯西不等式,求導)

 3.反函數求導法則

LeetCode343之整數拆分(相關話題:數學柯西不等式,求導)

4.複合函數求導法則  

LeetCode343之整數拆分(相關話題:數學柯西不等式,求導)

數學類題目需要了解推導過程,并且記住一般性結論,有機會的話在其他場景下重複應用才能了解深刻。