iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 29
2
Software Development

動態規劃百題之經典、理論與實作系列 第 29

Day 29: 利用一點點的貪婪演算法提升動態規劃效能!

如果說,動態規劃是個穩穩地將所有可能的狀態逐一計算、集中並且化簡。那麼貪婪法(Greedy Algorithm) 就是另一個方向:通常僅考慮一小部分的狀態計算,因為我們能夠證明依照當前的最佳的選擇就是對整體來說最好的選擇。

有的時候,利用這個想法,我們可以利用數學證明減少需要計算的狀態數!最單純的例子就是 LCS 在解很大的時候的 O((n-LCS)n+1) 時間解法:我們只要考慮對角線附近的格子就行了。

Exercise 44: Leetcode 321 - Create Maximum Number

題目連結

https://leetcode.com/problems/create-maximum-number/

題目敘述

給你兩個陣列的數字,請從中挑出 k 個數字拼起來得到最大的十進位數字。拼起來的時候挑出來的數字必須要保持在兩陣列中的順序。

解題思考

通常在解字典順序的時候,我會喜歡從陣列的末端做回來。我們令 dp(i, j, r) 表示用 A[i...] 和 B[j...] 湊出長度為 r 的序列時,最大的一個序列是多少。

dp(i, j, r) ← dp(i+1, j, r) or dp(i, j+1, r) or A[i]+dp(i+1, j, r-1) or B[j] + dp(i, j+1, r-1)

但可惜這樣是 O(N^2K^2) 的,可能會超過時間。

換一個方法想,如果我們枚舉第一個陣列強迫選 r 個,另外一個陣列強迫選 k-r 個。各自湊出字典順序最大的陣列,再用貪婪的方法合併起來就可以得到一個 O(K^2(N+K)) 時間的演算法了!

參考程式碼 (Python3)

class Solution:

    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:

        def merge(a, b):
            c = []
            while len(a) > 0 or len(b) > 0:
                if a > b:
                    c.append(a.pop(0))
                else:
                    c.append(b.pop(0))
            return c

        def getMaxNumberByLength(a):
            l = [[]]
            for x in a:
                l.append(l[-1] + [x])
                for j in range(len(l)-3, -1, -1):
                    if l[j] + [x] > l[j+1]:
                        l[j+1] = l[j] + [x]
            return l

        l1 = getMaxNumberByLength(nums1)
        l2 = getMaxNumberByLength(nums2)
        ans = []
        for i in range(0, k+1):
            if len(l1) <= i or len(l2) <= k-i:
                continue
            p = merge(l1[i], l2[k-i])
            if p > ans:
                ans = p
        return ans

merge 函式很酷,可以合併成一行文:

def merge(a, b):
        return [max(a, b).pop(0) for _ in range(len(a) + len(b))]

上一篇
Day 28: 透過鋪磚塊問題來看看動態規劃可運用之處!
下一篇
Day 30: 那些沒有提到的動態規劃和還沒做完的題目。
系列文
動態規劃百題之經典、理論與實作30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言