# -*- coding: utf-8 -*-
# 476. Stone Game
# There is a stone game.At the beginning of the game the player picks n piles of stones in a line.
#
# The goal is to merge the stones in one pile observing the following rules:
#
# At each step of the game,the player can merge two adjacent piles to a new pile.
# The score is the number of stones in the new pile.
# You are to determine the minimum of the total score.
#
# Example
# Example 1:
#
# Input: [3, 4, 3]
# Output: 17
# Example 2:
#
# Input: [4, 1, 1, 4]
# Output: 18
# Explanation:
#   1. Merge second and third piles => [4, 2, 4], score = 2
#   2. Merge the first two piles => [6, 4]，score = 8
#   3. Merge the last two piles => [10], score = 18


class Solution:
    """
    @param A: An integer array
    @return: An integer
    """

    def stoneGame(self, A):
        if not A:
            return 0
        N = len(A)
        rSum, dp = [[0] * N for _ in xrange(N)], [[0] * N for _ in xrange(N)]

        for i in xrange(N):
            rSum[i][i] = A[i]
        for i in xrange(N):
            for j in xrange(i + 1, N):
                rSum[i][j] = rSum[i][j - 1] + A[j]

        for l in xrange(1, N):
            for start in xrange(N):
                end = start + l
                if end >= N:
                    continue

                dp[start][end] = float('inf')
                for k in xrange(start, end):
                    dp[start][end] = min(dp[start][end], dp[start][k] + dp[k + 1][end] + rSum[start][end])

        return dp[0][-1]


if __name__ == '__main__':
    print Solution().stoneGame([3, 4, 3])
