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 For [4, 1, 1, 4], in the best solution, the total score is 18:

1. Merge second and third piles => [4, 2, 4], score +2
2. Merge the first two piles => [6, 4]，score +6
3. Merge the last two piles => [10], score +10 Other two examples: [1, 1, 1, 1] return 8 [4, 4, 5, 9] return 43

Tags Related Problems Code editor is not visible on small screen.

思路：dp[i][j]代表从第i到j个石头，最小的得分。递推公式：

dp[i][j]= sum(num[i:j]) + min([dp[i][k]+dp[k+1][j] for k in range(i,j)])。

公式可以这样理解，从i到j石头的最小得分等于把这堆石头分成两堆的所有得可能里面取最小的。因为最后还要合并一次，所以需要加sum(nums[i:j])。因为是从上往下拆分，所以不难理解用dfs来做。并且用memo来存储已经计算过的结果。代码也非常好理解呢！

jiuzhang http://www.lintcode.com/en/problem/stone-game/

class Solution(object):
    def stoneGame(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums: return 0
        self.memo = [[0]*len(nums) for _ in range(len(nums))]
        return self.dfs(nums, 0, len(nums)-1)

    def dfs(self, nums, i, j):
        if i==j: return 0

        if not self.memo[i][j]:
            tmp = [self.dfs(nums, i, k) + self.dfs(nums, k+1, j) for  k in range(i, j)]
            self.memo[i][j] = sum(nums[i:j+1]) + min(tmp)

        return self.memo[i][j]

so = Solution()
print so.stoneGame([4, 1, 1, 4])