个人中心
gpt4 book ai didi

312. Burst Balloons 戳气球

转载 作者：大佬之路 更新时间：2024-01-31 14:20:25 28 4
gpt4 key购买 nike

题目地址: https://leetcode.com/problems/burst-balloons/description/

题目描述：

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:

  • You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
  • 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Input: [3,1,5,8]
Output: 167 
Explanation: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
             coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

题目大意

打气球游戏，当我们打某个位置的气球的时候，能获得它左右两个气球上的分数和自身分数的乘积。问如何打气球能获得最多的分数？可以认为最左右两边隐含着分数为1不用打破的气球。

解题方法

这个是个DP的题目，当然也可以通过记忆化搜索的方式解决。

令dfs(i, j) 和 c[i][j]是在第[i, j]闭区间上打破气球能获得最大值。那么，在其中找到一个不打破的气球k，则可以得到以下关系：

c[i][j] = max(c[i][j], self.dfs(nums, c, i, k - 1) + nums[i - 1] * nums[k] * nums[j + 1] + self.dfs(nums, c, k + 1, j))

含义是，我们找出在[i, k - 1]、[k + 1, j]闭区间打气球的分数最大值，然后会把第i - 1和第j + 1个气球保留下来，让这两个气球和第k个气球相乘，最后求三个加法。

模拟左右两边的气球的方法是直接添加上首尾各一个1，同时使用记忆化能加速不少，也为下一步的DP提供思路。

时间复杂度是O(N^2 * log(N))(不会算…)，空间复杂度是O(N)。

class Solution(object):
    def maxCoins(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        nums.insert(0, 1)
        nums.append(1)
        c = [[0] * (n + 2) for _ in range(n + 2)]
        return self.dfs(nums, c, 1, n)
        
    def dfs(self, nums, c, i, j):
        if i > j: return 0
        if c[i][j] > 0: return c[i][j]
        if i == j: return nums[i - 1] * nums[i] * nums[i + 1]
        res = 0
        for k in range(i, j + 1):
            res = max(res, self.dfs(nums, c, i, k - 1) + nums[i - 1] * nums[k] * nums[j + 1] + self.dfs(nums, c, k + 1, j))
        c[i][j] = res
        return c[i][j]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

第二种解法是使用DP。

DP一般都可以通过记忆化搜索来改出来，但是我不会。。很遗憾，参考了别人的代码，还是没搞懂。。

class Solution(object):
    def maxCoins(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        nums.insert(0, 1)
        nums.append(1)
        dp = [[0] * (n + 2) for _ in range(n + 2)]
        for len_ in range(1, n + 1):
            for left in range(1, n - len_ + 2):
                right = left + len_ - 1
                for k in range(left, right + 1):
                    dp[left][right] = max(dp[left][right], dp[left][k - 1] + nums[left - 1] * nums[k] * nums[right + 1] + dp[k + 1][right])
        return dp[1][n]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

参考资料：

http://www.cnblogs.com/grandyang/p/5006441.html https://www.youtube.com/watch?v=z3hu2Be92UA

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发

28 4 0
文章推荐： 328. Odd Even Linked List 奇偶链表
文章推荐： 219. Contains Duplicate II 存在重复元素 II
文章推荐： 205. Isomorphic Strings 同构字符串
文章推荐： 320. Generalized Abbreviation 列举单词的全部缩写
大佬之路
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com