Leetcode 312. Burst Balloons

Problem

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

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

Algorithm

Dynamic Programming (DP). Let dp[s][t] represent the maximum number of coins that can be obtained by bursting all the balloons between index s and t.
$$dp[s][t]=max(dp[s][k]+dp[k][t]+nums[s]\ast nums[k]\ast nums[t])$$

For $s<k<t$.

Code

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        nums = [1] + nums + [1]
        nlen = len(nums)
        dp = [[0] * nlen for _ in range(nlen)]
        
        for l in range(2, nlen):
            for s in range(nlen - l):
                t = s + l
                for k in range(s+1, t):
                    if dp[s][t] < dp[s][k] + dp[k][t] + nums[s] * nums[k] * nums[t]:
                        dp[s][t] = dp[s][k] + dp[k][t] + nums[s] * nums[k] * nums[t]
        
        return dp[0][nlen - 1]

原文地址：https://blog.csdn.net/mobius_strip/article/details/146445289

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！