Zenefits電面真題 & 解析

專欄 | 九章演算法

網址 | http://www.jiuzhang.com

2015年10日22日剛面的zenefits電面題：

一堆商品，買一個可以送一個，但送的那個的價格必須小於買的那個的價格（強調一下，不能等於）。給定商品總數n和每個商品的價格，求得到全部商品的最少開銷。 例如：4個商品價格為[5, 4, 3, 3]，最優解為9，即買5和4，送3和3。 兩個test case: [100, 99, 98, 1, 1, 1], [100, 99, 98, 98, 97, 97, 97, 97]

更多面試真題，請訪問九章官網QA版塊。

解 答

令狐沖，九章演算法班主講老師

這個題確實是很難的動態規劃。屬於區間型動態規劃。在九章演算法強化班中會講到這個類型的動態規劃。

首先排序不用說了。從小到大（從大到小也可以，我比較喜歡從小到大）。然後先給出DP的方程：

定義狀態 f[i][j] 為 i 到 j 這一段的最優值（最少花多少錢全買下來）nf[i][j] = min(f[i + 1][j - 1]+A[j], f[i][k] + f[k+1][j]) 其中k為i到j-1。n

然後我們來證明為什麼這個方程是對的。這個方程的假設前提是，不存在相交的搭配，也就是說不存在下面這種情況的匹配：

從小到大的4個數：a<= b<= c<= d。 a與c一起買，b與d一起買。n

為毛呢？首先a和d肯定不相等，否則的話，abcd都相等了，這種情況是不會出現的（我們就是要證明這種情況不會出現），然後看b和c，如果他們相等，那麼換成(a,b)和(c,d)，代價一樣，並且不會產生相交的匹配（什麼叫做相交？你在ac連一條曲線，和bd之間的曲線一定相交）。然後看b和c不等的情況，不等的話，換成(b,c) + (a,d)，也還是不影響結果=c+d， 然後又能使得連線不相交。

好了，上面我們證明了不相交理論。那麼既然連線不想交的話，i-j這一段的匹配情況，只存在兩種可能性：

• 第一種可能是i和j匹配，然後中間的自己配對。

• 第二種可能是，一定存在一條分割線，使得這個i-j的區間被分為i-k和k+1-j，兩個區間之間的自己匹配，沒有互相的連邊。

好了，綜上所述。問題已經解決並證明。我知道理解起來有點難，特別是證明，我也證明了好久……

順便說一下時間複雜度 ： O(n^3)，可能可以用決策單調的優化優化到O(n^2)。

你可能要問我，我TMD是怎麼想到這個解法的呢？因為課上講過的DP就那麼幾種大類型……面試99%都落在 「劃分/區間/矩陣/雙序列/背包" 這五種類型。一個個試試看就行了……首先想到的是劃分，然後發現推導不出來。然後矩陣肯定不是，雙序列和背包也不是，只剩下區間了……

歡迎關注我的微信公眾號：九章演算法（ninechapter）。

精英程序員交流社區，定期發布面試題、面試技巧、求職信息等。

aHR0cDovL3dlaXhpbi5xcS5jb20vci9zVVBsLVlURVM5azByY0NlOXhhag== (二維碼自動識別)

推薦閱讀：