def maxCoins(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# 状态res[left][right]代表把left到right之间的气球戳破(不包括left和right)能获得的最大收益
# 转移方程: res[left][right] = max(res[left][k] + res[k][right] + nums[left] * nums[k] * nums[right])
# k从left+1到right(不包括right)
# 这题的特点是转移方程不是一个简单的公式,而是for循环求max获得的
if len(nums) == 0:
return 0
if len(nums) == 1:
return nums[0]
n = len(nums) + 2
res = []
for i in range(n):
temp = [0] * n
res.append(temp)
temp = nums
nums = [1]
nums.extend(temp)
nums.append(1)
for delta in range(2, n):
for left in range(n - delta):
right = left + delta
tmp = []
for k in range(left + 1, right):
tmp.append(res[left][k] + res[k][right] + nums[left] * nums[k] * nums[right])
res[left][right] = max(tmp)
return res[0][n - 1]
312戳气球
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 这是一道很经典的题目。dp状态的确定和推导都比较难想，但如果见多了，就熟了。这题难点在于你扎气球时不知道左右两边最...
