Lintcode 石子归并

class Solution:
    """
    @param A: An integer array
    @return: An integer
    """
    def stoneGame(self, A):
        # write your code here
        if not A:
            return 0
        n = len(A)
        dp = [[float("inf")] * n for _ in range(n)]
        dp[0][0] = 0 
        for i in range(n):
            for j in range(i, -1, -1):
                if i == j:
                    dp[j][i] = 0
                else:
                    s = sum(A[j:i+1])
                    for k in range(j, i):
                        dp[j][i] = min(dp[j][i], dp[j][k] + dp[k+1][i] + s)
        return dp[0][-1]