'''
記憶化搜索，分治
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] 維護一個 角標 i 存著這個 List[int] 0 ~ i 的數(shù)的和，方便通過O(1)減法得到區(qū)間和。
環(huán)
因為是圓形操場，輸入為 [4,5,9,4] 的話，存在把 [4,4] 合并的情況，學過離散數(shù)學的同學應(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的窗口，每移動一位，就能復現(xiàn)上面環(huán)的各種情況。括號里面的0 和 4 加進來用于處理邊界情況，更方便利用前綴和來獲得區(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ū)間的最小代價。
當兩個子區(qū)間帶著各自的代價形成，最后形成 [i,j]，無論兩個子區(qū)間是怎樣的，根據(jù)定義，這一步合成的代價一定就是[i,j] 的石子總和，可以通過前綴和輕松求出。

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

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