CodingTour —

ARTS #123

Algorithm

本周选择的算法题是：Burst Balloons。

规则

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.

Example 1:

Input: nums = [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

Example 2:

Input: nums = [1,5]
Output: 10

Constraints:

• n == nums.length
• 1 <= n <= 500
• 0 <= nums[i] <= 100

Solution

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        if len(nums) > 1 and len(set(nums)) == 1:
            return (nums[0] ** 3) * (len(nums) - 2) + nums[0] ** 2 + nums[0]
      
        nums = [1] + [num for num in nums] + [1]
        n = len(nums)
        dp = [[0] * n for _ in range(n)]

        for i in range(2, n):
            for left in range(0, n - i):
                right = left + i
                for j in range(left + 1, right):
                    dp[left][right] = max(
                        dp[left][right],
                        nums[left] * nums[j] * nums[right] + dp[left][j] + dp[j][right]
                    )
        return dp[0][-1]

Review

How to document software architecture?

一篇介绍如何写软件架构文档的文章。

架构设计能力，因掌握起来困难而显得珍贵，不同的角色对架构的关注点不同，架构图很难以一概全，要了解自己目标用户的角色，运用不同的设计工具为每个角色提供最清晰的架构指导。

Tip

苹果的坑：NSDateFormatter and Internet Dates，如果 NSDateFormatter 不指定 locale 可能会被系统覆盖 format string。

Share

为祖国庆生！