有n个气球，编号为0到n-1，每个气球都有一个分数，存在nums数组中。每次吹气球i可以得到的分数为 nums[left] * nums[i] * nums[right]，left和right分别表示i气球相邻的两个气球。当i气球被吹爆后，其左右两气球即为相邻。要求吹爆所有气球，得到最多的分数。

---

　　

 1 class Solution:
 2     """
 3     @param nums: A list of integer
 4     @return: An integer, maximum coins
 5     """
 6     def maxCoins(self, nums):
 7         # write your code here
 8         nums = [1] + nums + [1]
 9         score = [[0 for j in range(len(nums))] for i in range(len(nums))]
10         
11         # score[i][j]表示打掉[i+1, j-1]的气球后得到的最大分数
12         # 递推式
13         # score[i][j] = max(score[i][j], score[i][k] + score[k][j] + nums[i] * nums[k] * nums[j]) (i<k<j)
14         
15         for interval in range(3, len(nums) + 1):
16             for i in range(len(nums)):
17                 j = i + interval - 1
18                 if j >= len(nums):
19                     break
20                 for k in range(i + 1, j):
21                     score[i][j] = max(score[i][j], score[i][k] + score[k][j] + nums[i] * nums[k] * nums[j])
22         
23         return score[0][len(nums) - 1]
24