動機

分治與dp在轉念之間

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.

 

Example 1:

Input: nums = [3,1,5,8]Output: 167Explanation: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

思路

如果只看這個位置的最大分數，會發現整個變成分治後遞迴，之後TLE

為什麼會變成分治? 爆完一顆氣球後就變成兩邊了!!

有什麼是連續的，不是像還沒爆完的氣球，分成兩邊? 已經爆完的氣球都是在一起的!!

所以要變成看這個範圍的最大分數，分數就變成，

f[i..j] <= i~j都被爆完後的最大分數
=
score[i-1]*score[j+1]*score[k] <= 從k爆後的分數
+
f[i..k] <= 左邊的最大分數 (因k已經被爆了，所以要包進來不能是f[i..(k-1)]
+
f[k..j] <= 右邊的最大分數

可以想成把所有單點爆的解都收在一起，去列舉去找

Ver1: hash

超慢，大概1400ms，用hash這麼慢??

裡面是不是用hash function實作的? python對大塊的資料做操作時效能都很悲劇

def def_list(l,i):
    if i < 0:
        return 1
    try:
        return l[i]
    except IndexError:
        return 1
# 一般作二分，會把重點放在兩邊，但不是分割點
# 不過這次的重點是分割點
class Solution:
    def maxCoins(self, ns: List[int]) -> int:
        if not ns:
            return 0
        dp = {}
        for i in range(0,len(ns)):
            dp[(i,i)] = ns[i]*def_list(ns,i-1)*def_list(ns,i+1)
        for k in range(1,len(ns)):
            for i in range(0,len(ns)-k):
                j = i+k
                #print(i,j)
                if j < len(ns):
                    for x in range(i,j+1):
                        dp[(i,j)] = max(dp.get((i,j),0), dp.get((i,x-1),0)+dp.get((x+1,j),0)+ns[x]*def_list(ns,j+1)*def_list(ns,i-1))
        print(dp)
        return dp[(0,len(ns)-1)]

Ver2: array

改用傳統手法就好多了

class Solution:
    def maxCoins(self, ns: List[int]) -> int:
        if not ns:
            return 0
        ns = [1, *ns, 1]
        dp = [[0]*(len(ns)) for i in range(len(ns))]
        for i in range(1,len(ns)-1):
            dp[i][i] = ns[i]*ns[i-1]*ns[i+1]
        dp[0][0] = ns[1]
        dp[-1][-1] = ns[-2]
        for k in range(2,len(ns)):
            for i in range(0,len(ns)-k):
                j = i+k
                for x in range(i+1,j):
                    dp[i][j] = max(dp[i][j], ns[i]*ns[j]*ns[x]+dp[i][x]+dp[x][j])
        #print(dp)
        return dp[0][-1]

case study: top-down

超漂亮，還用到了

  1. functools.lru_cache: 這樣就不用自己設table
  2. for-range: 直接用在max上!!
class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        nums = [1] + nums + [1]
        
        @functools.lru_cache(None)
        def dp(left, right):
            if left + 1 == right:
                return 0
            return max(
                nums[left] * nums[i] * nums[right] + dp(left, i) + dp(i, right)
                for i in range(left+1, right)
            )
        
        return dp(0, len(nums)-1)