'''
记忆化搜索，分治
P1880 [NOI1995]石子合并 @ LuoGu
https://www.luogu.org/problemnew/show/P1880
题目描述
在一个**圆形操场**的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选**相邻**的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.

输入输出格式
输入格式：
数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.

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

输入输出样例
输入样例#1： 
4

输出样例#1： 
43
54
'''

可能对新人（OIer && ACMer请绕道）有用的新概念

前缀和
对应一个 List[int] 维护一个 角标 i 存着这个 List[int] 0 ~ i 的数的和，方便通过O(1)减法得到区间和。
环
因为是圆形操场，输入为 [4,5,9,4] 的话，存在把 [4,4] 合并的情况，学过离散数学的同学应该看过圆桌问题（一个桌子5个人，能坐多少种不同的顺序），这就需要引入一个大一点的序列以便处理环现象。

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的窗口，每移动一位，就能复现上面环的各种情况。括号里面的0 和 4 加进来用于处理边界情况，更方便利用前缀和来获得区间和

记忆化搜索有的地方也叫分治法，在国外这手段也被归并到动态规划。不过因为涉及递归，所以比一般的顺序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 : 区间始
        j : 区间末
        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

区间DP的思想

其实很简单
通过递归来把大区间[i,j]， 以 i <= c <j 为分界线，划分 子区间 [i,c], [c+1,j]
self.dp_min(i,c)，self.dp_min(c+1,j) 为两个子区间的最小代价。
当两个子区间带着各自的代价形成，最后形成 [i,j]，无论两个子区间是怎样的，根据定义，这一步合成的代价一定就是[i,j] 的石子总和，可以通过前缀和轻松求出。

BASE CONDITION
self.min_memo[i][i] = 0, 只能代表当前单独第 i 堆，无任何合并操作，所以不会产生任何代价。
self.min_memo[i][i+1] 则是两堆石子合并，其实最终也就通过前缀和来求。

大佬巨佬们多多指教小弟做人，我写这个主要想把所思所想记录下来，有不少新概念和操作都是看过大神们提一提才慢慢懂。这篇算是小白文吧，毕竟我想通过简书或者CSDN搜，大佬们都写得像是准备给水平已经很不错的读者。