周五來了，即將快樂周末，今天就給大家分享一道有趣的算法題，希望能給大家?guī)硪粋€好心情～
故事，要從住在森林里的大熊發(fā)現(xiàn)了一個裝滿蘋果的山洞說起...
我發(fā)現(xiàn)一個山洞，里面有好多蘋果??，看起來很好吃的樣子～
不過我們只能從洞口和洞尾拿蘋果，我們來比比看誰拿的蘋果重量最大吧～
熊熊們山洞之旅遇到的問題，歸納起來就是：給定一個裝滿蘋果的山洞，只能從洞口和洞尾拿蘋果，每輪兩只熊交替拿，并且只能拿一個，誰拿的蘋果總重量最大誰就獲勝，那誰會是最終的贏家呢？
假定山洞里蘋果的分布為：1KG，3KG，14KG，7KG。
直覺上來說，是不是我們每輪拿最大的，就一定贏？如果是這種策略，那么大熊第一輪拿7KG，此時的狀況就變成了：
現(xiàn)在山洞里只剩下1KG和3KG兩個蘋果，無論大熊拿哪一個，它手上蘋果總重量，也沒二熊的重。難道這是大熊的必輸局？
如果第一輪，大熊選擇拿第一個蘋果，那此時狀態(tài)就變成了：
這個時候，二熊只能從3KG、7KG里面選，無論拿哪個，大熊第三輪拿到14KG都能獲勝。因此，只要開局拿1KG，大熊就是必勝的。
所以說，每輪選最大這種策略行不通，我們還需要考慮到對后面蘋果的影響。
相信經過這個分析，大家已經對題目比較清楚，甚至有點解題思路了吧？別著急，現(xiàn)在我們就一起來看看有哪些解決辦法吧。
深度優(yōu)先遞歸法
我們可以把問題抽象出來，大熊第一輪去取蘋果，是否能贏取決于兩個因素：一個是取的蘋果的重量，另一個是二熊對剩下的進行選擇。再仔細一想，二熊面臨的問題，其實和大熊開始時是一模一樣的。這樣思路就很明顯了，我們可以用遞歸的方法去解決問題。我們從最右邊往左邊看，每一輪都選擇當前的最優(yōu)解，整個流程走下來，就是遞歸的實際執(zhí)行流程了。func CanFistBearWin(nums []int) bool { return picker(0, len(nums)-1, nums) >= 0}
func picker(i, j int, nums []int) int { if i == j { return nums[i] } head := nums[i] - picker(i+1, j, nums) end := nums[j] - picker(i, j-1, nums) return max(head, end)}
記憶化遞歸法
問題雖然解決了，但是跑了一下測試用例，發(fā)現(xiàn)用時100ms以上。這樣看來，性能上是不是還有優(yōu)化空間呢？可以看到，圖上是有重復子問題的，那我們完全可以將子問題的解答記錄下來。等到后面再遇到的時候，直接返回結果，而不用再遞歸下去，這樣就可以節(jié)約大量時間了。
動態(tài)規(guī)劃法
在上面的分析中，我們已經把問題拆分為子問題，既然是子問題，又可以遞歸解決，那么就不由地會去想，能不能通過動態(tài)規(guī)劃，遞推解決？依照慣例，我們需要一個dp數(shù)組，在上面的分析中不難看出，這個數(shù)組應該是二維的，dp[i][j]就表示左邊起點為i，右邊起點為j的山洞，在先手的情況下，熊熊能拿多少KG的蘋果。
既然要用動態(tài)規(guī)劃，那么一定要找到一個公式。我們前面分析過，如果大熊先手，是否能贏取決于兩個因素：一個是取的蘋果的重量，另一個是二熊對剩下的進行選擇。dp[i][j] = Max(nums[i]-dp[i+1][j], nums[j]-dp[i]dp[j-1])再結合下面的圖來進行推導。我們還是以四個蘋果為例，為蘋果從左到右編上號。
0號位置對應的dp[0][0]就是其蘋果的重量，我們從1號位置開始，對每個位置往前遞推：
func CanFistBearWin(nums []int) bool { length := len(nums) dp := make([][]int, length) for i := 0; i < length; i++ { dp[i] = make([]int, length) dp[i][i] = nums[i] } for j := 1; j < length; j++ { for i := j-1; i >= 0; i-- { head := nums[i] - dp[i+1][j] end := nums[j] - dp[i][j-1] dp[i][j] = max(head, end) } } return dp[0][length-1] >= 0}
果不其然，成功拿到了蘋果，熊熊開心地跳起了舞
解決此類問題的核心思想，是將從洞兩端選擇蘋果這個問題抽離出來，成為子問題。然后，在此基礎上，我們建立了遞歸解法，根據(jù)實際運行的結果，使用記憶化搜索優(yōu)化，提高了性能。解決了問題就算完成任務了？我們的目標可是成為一名追求極致的工程師，當然會想還有沒有其它解決方案。于是，我們將同一種抽象模型，從遞歸轉換成遞推，玩了把動態(tài)規(guī)劃。換個角度看問題，生命會展現(xiàn)出另一種美。生活中不是缺少美，而是缺少發(fā)現(xiàn)。算法也一樣，同一個問題，學著用多個角度去思考、解決，你會發(fā)現(xiàn)它別樣的魅力！
