Stone Game

这道题算是区间DP的经典题型了，此问题属于不容易由小到大递推的题目，应该把思路转为由大到小来递推，首先我们要求的结果是dp[0][n - 1]，然后可以思考最后一步的时候，合并的总值必然就是整个数组的和，也就意味着最后一步无论如何合并都是要加上一个这个耗费的，再因为最后一步时必然只可能剩下两块合并过后的石子，所以可以推得一个很明显的状态转移方程如下

for index in xrange(i, j):
    dp[i][j] = min(dp[i][index] + dp[index + 1][j] + sum[i][j], dp[i][j])

用这个状态转移方程可以很容易求得结果了，另外注意这题需要先求得一个sum矩阵来记录所有i-j区间的数值总和，还需要一个flag矩阵来记录是否已经搜索过这个区间（这也是记忆化搜索做dp问题必须要有的一个辅助矩阵），下面是代码

class Solution:
    # @param {int[]} A an integer array
    # @return {int} an integer
    def stoneGame(self, A):
        # Write your code here
        n = len(A)
        if n <= 1:
            return 0

        ref = [([0] * n) for _ in xrange(n)]
        for i in xrange(n):
            for j in xrange(i, n):
                ref[i][j] = ref[i][j - 1] + A[j] if i != j else A[i]

        flag = [([False] * n) for _ in xrange(n)]
        dp = [([0] * n) for _ in xrange(n)]
        return self.memoiz(0, n - 1, flag, ref, dp)

    def memoiz(self, i, j, flag, ref, dp):
        if flag[i][j]:
            return dp[i][j]

        flag[i][j] = True
        if i == j:
            return dp[i][j]
        elif i > j:
            return 0
        else:
            tmp = sys.maxint
            for index in xrange(i, j):
                tmp = min(self.memoiz(i, index, flag, ref, dp) +
                     self.memoiz(index + 1, j, flag, ref, dp) +
                     ref[i][j], tmp)
            dp[i][j] = tmp
            return dp[i][j]

现在已经完全不习惯写记忆化搜索了，区间DP是完全可以用for循环递推写的

class Solution:
    """
    @param: A: An integer array
    @return: An integer
    """
    def stoneGame(self, A):
        # write your code here
        n = len(A)
        if not n:
            return 0

        dp = [[0] * n for _ in xrange(n)]

        for i in xrange(n):
            for j in xrange(i, -1, -1):
                if i == j:
                    dp[j][i] = 0
                elif j + 1 == i:
                    dp[j][i] = A[j] + A[i]
                else:
                    base = sum(A[j : i + 1])
                    dp[j][i] = sys.maxint
                    for k in xrange(j, i):
                        dp[j][i] = min(dp[j][k] + dp[k + 1][i] + base, dp[j][i])

        return dp[0][n - 1]

Stone Game II

现在可以用前后接在一起合并了怎么办？一开始肯定会想直接模n做就行了，但是这题这么做答案不对，我自己也不是很知道为什么不对，区间的题目细节太复杂了，以后处理环的问题，要不把环拆断（house robber II），要不就像这道题把环的头尾接上变成直线再做，另外因为这里长度变成了2n，所以我们相当于还是在找j小于等于i的所有情况，矩阵还是半边没有用，然后我们最后的结果是在任何一个j和i的差为n的区间里面的最小值

class Solution:
    # @param {int[]} A an integer array
    # @return {int} an integer
    def stoneGame2(self, A):
        # Write your code here
        if not A:
            return 0

        n = len(A)
        dp = [[0] * (2 * n) for _ in xrange(2 * n)]
        A += A

        for i in xrange(2 * n):
            for j in xrange(i, i - n, -1):
                if j == i:
                    dp[j][i] = 0
                elif j + 1 == i:
                    dp[j][i] = A[j] + A[i]
                else:
                    dp[j][i] = sys.maxint
                    base = sum(A[j : i + 1])                    
                    for k in xrange(j, i):
                        dp[j][i] = min(dp[j][i], dp[j][k] + dp[k + 1][i] + base)

        result = sys.maxint
        for i in xrange(n):
            result = min(result, dp[i][i + n - 1])            
        return result