Changchun Master Li

一张表教会小学生轻松理解
leetcode 312 Burst Balloons

2017-12-14

如果有一天我面试别人, 如果我想拒绝他, 我会让他做这道题.

题目

言归正传, 题目大意是有 n 个气球, 一个数组 nums 位置从 0 到 n - 1 表示气球上的数字.
戳破气球 i 可以得到值为 nums[i - 1] * nums[i] * nums[i + 1] 的奖励.
nums[-1] = nums[n] = 1, 不能戳破边界.
0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

对于一个数组 nums 求最大奖励.

分析

  • brute force 不可行, 因为最坏时间复杂度为 O(n!) , n 的规模大于 10 就会很慢.
  • 于是我开始用一些启发式搜索算法来剪枝, 对于相邻的 [a, b, c, d] ,
    尝试进一步通过 a * b * (c - d) + (a - b) * c * d 来确定 b 和 c 的优先级, 找到拐点. 然而这是个大坑, 想了一晚上也没搞明白.
    如果沿着这个方向去想直接 gg
  • 其实, 结果不依赖与已经戳破的气球. 我们可以试图定义一个子问题来解决这个问题.
    动态规划 才是正确的姿势

一张dp表解决问题

例如 nums = [3,1,5,8]
首尾补上 1 为 [1,3,1,5,8,1]

dp[r][l] 的意义为 以 nums[r] 和 nums[l] 为边界的最大奖励, 即求 dp[0][5]

不过这个 dp 比较递推关系比较巧妙:
首先更新对角线元素, 对角线值固定, 都是 0.
然后从对角线往右上角更新,
对于所有 r < i < l, dp[r][l] = max(nums[i - 1] * nums[i] * nums[i + 1] + dp[r][i] + dp[i][l])

找到了方法, 完成代码就十分轻松愉快了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def maxCoins(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = [1] + nums + [1]
        cache = dict()
        for k in range(1, len(nums)):
            for l in range(0, len(nums) - k):
                r = l + k
                if k == 1:
                    cache[(l,r)] = 0
                elif k == 2:
                    cache[(l,r)] = nums[l]*nums[l + 1]*nums[l + 2]
                else:
                    cache[(l,r)] = 0
                    for i in range(l+1, r):
                        cache[(l,r)] = max( \
                        	cache[(l,r)], \
                        	nums[l]*nums[i]*nums[r] \
                        	+ cache[(l,i)] + cache[(i,r)] \
                        )
        return cache[(0, len(nums)-1)]
Tags: algorithm leetcode
← confusing python <br> <del>Python 程序员如何避免被炒鱿鱼</del> 使用homebrew的正确姿势 →
赏
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏

扫描二维码，分享此文章