'''
記憶化搜索根资，分治
P1880 [NOI1995]石子合并 @ LuoGu
https://www.luogu.org/problemnew/show/P1880
題目描述
在一個**圓形操場**的四周擺放N堆石子,現(xiàn)要將石子有次序地合并成一堆.規(guī)定每次只能選**相鄰**的2堆合并成新的一堆偷溺，并將新的一堆的石子數(shù)，記為該次合并的得分。

試設(shè)計出1個算法,計算出將N堆石子合并成1堆的最小得分和最大得分.

輸入輸出格式
輸入格式：
數(shù)據(jù)的第1行試正整數(shù)N,1≤N≤100,表示有N堆石子.第2行有N個數(shù),分別表示每堆石子的個數(shù).

輸出格式：
輸出共2行,第1行為最小得分,第2行為最大得分.

輸入輸出樣例
輸入樣例#1： 
4

輸出樣例#1： 
43
54
'''

可能對新人（OIer && ACMer請繞道）有用的新概念

前綴和
對應(yīng)一個 List[int] 維護(hù)一個 角標(biāo) i 存著這個 List[int] 0 ~ i 的數(shù)的和，方便通過O(1)減法得到區(qū)間和。
環(huán)
因為是圓形操場晒他，輸入為 [4,5,9,4] 的話悉罕，存在把 [4,4] 合并的情況，學(xué)過離散數(shù)學(xué)的同學(xué)應(yīng)該看過圓桌問題（一個桌子5個人掌逛，能坐多少種不同的順序）师逸，這就需要引入一個大一點的序列以便處理環(huán)現(xiàn)象。

4 5 9 4 -> 5 9 4 4 -> 9 4 4 5 -> 4 4 5 9 -> (4, 5, 9, 4)
那么簡化一下豆混，可以得到
石頭：    [(0), 4, 9, 5, 4, 4, 9, 5, (4)]篓像，和
前綴和：[0, 4, 13, 18, 22, 26, 35, 40, 44]

你可以想象一個長為4的窗口，每移動一位皿伺，就能復(fù)現(xiàn)上面環(huán)的各種情況员辩。括號里面的0 和 4 加進(jìn)來用于處理邊界情況，更方便利用前綴和來獲得區(qū)間和

記憶化搜索有的地方也叫分治法鸵鸥，在國外這手段也被歸并到動態(tài)規(guī)劃奠滑。不過因為涉及遞歸，所以比一般的順序DP會慢一點妒穴。
上代碼宋税，這里只做min的情況，max的話基本上就是這個的映射版：

class Solution(object):
    def getSum(self,i,j):
        return self.s[j] - self.s[i-1]
    def mergeStone(self,nums):
        '''
        nums : List[int]
        '''
        n = len(nums)
        s = []
        nums = [0] + nums + nums
        L = 1
        R = 2*n
        s = [i for i in nums]
        for i in range(1,len(s)):
            # 前綴和
            s[i] = s[i-1] + s[i]
        self.s = s
        # extra 1 for lower limit. 
        self.min_memo = [[None for b in range(n+n+1)] for a in range(n+n+1)]
        
        self.dp_min(L,R)
        minres = float('inf')
        for i in range(1,n+1):
           minres = min(minres,self.min_memo[i][i+n-1])
        print(minres)
    def dp_min(self,i,j):
        '''
        i : 區(qū)間始
        j : 區(qū)間末
        s : 前綴和讼油，用于訪問
        '''

        if j==i:
            self.min_memo[i][j] = 0
            return 0
        elif self.min_memo[i][j] != None:
            return self.min_memo[i][j]
        else:
            this_cost = self.getSum(i,j)
            tres = float('inf')
            for c in range(i,j):
                tres = min(tres,self.dp_min(i,c)+self.dp_min(c+1,j)+this_cost)
            self.min_memo[i][j] = tres
            return tres

區(qū)間DP的思想

其實很簡單
通過遞歸來把大區(qū)間[i,j]杰赛， 以 i <= c <j 為分界線，劃分 子區(qū)間 [i,c], [c+1,j]
self.dp_min(i,c)汁讼，self.dp_min(c+1,j) 為兩個子區(qū)間的最小代價淆攻。
當(dāng)兩個子區(qū)間帶著各自的代價形成，最后形成 [i,j]嘿架，無論兩個子區(qū)間是怎樣的瓶珊，根據(jù)定義，這一步合成的代價一定就是[i,j] 的石子總和耸彪，可以通過前綴和輕松求出伞芹。

BASE CONDITION
self.min_memo[i][i] = 0, 只能代表當(dāng)前單獨第 i 堆，無任何合并操作蝉娜，所以不會產(chǎn)生任何代價唱较。
self.min_memo[i][i+1] 則是兩堆石子合并，其實最終也就通過前綴和來求召川。

大佬巨佬們多多指教小弟做人南缓，我寫這個主要想把所思所想記錄下來，有不少新概念和操作都是看過大神們提一提才慢慢懂荧呐。這篇算是小白文吧汉形，畢竟我想通過簡書或者CSDN搜纸镊，大佬們都寫得像是準(zhǔn)備給水平已經(jīng)很不錯的讀者。