化繁為簡: 映射化簡的演算法技巧

演算法映射化簡的核心觀念

在面對新題目的時候，除了重頭想一個新的演算法之外；
還有另一個方法，想看看有沒有核心觀念彼此相同的問題與演算法，
如果有，就可以把新的題目映射化簡到已知解法的問題，用已知的演算法去解開。

接著，我們會介紹幾個範例，並且使用映射化簡的技巧來解題，透過化簡框架的復現，幫助讀者掌握這個知識點。

組合數之和 Combination Sum

題目給定目標值target，和一群整數candidates。
請問從中挑任意個數字做組合，允許重複選，有多少種方法可以讓組合數之和= target ?

把所有可能的組合方法列出來。

這題常見的方法是用DFS+回溯法去解，之前在專欄文章也解析過。

還有沒有別的解法呢? 其實有喔!

化簡到找零錢模型 Coin Change II

仔細觀察，用一群整數去湊出目標值target。

這個動作就相當於，用銅板去湊出目標金額amount!

整數就相當於銅板，每個整數對應到銅板的面額，例如一元、五元、十元。

目標值target就相當於目標金額amount。

那麼，這題組合數之和的問題，就被我們映射化簡到找零錢問題II Coin Change II

只要把所有能湊出target元的找零組合列出來，就是最終答案。

原本已知的Coin Change II的找零錢演算法和解題程式碼

class Solution:

    def change(self, amount: int, coins: List[int]) -> int:

        # base case:
        # amount 0's method count = 1 (by taking no coins)

        dp = [1] + [ 0 for _ in range(amount)]
       
        # make change with current coin, from small coin to large coin
        # 請注意看，等等我們會用 找零錢的演算法 去解開 組合數之和!
        for cur_coin in coins:
           
            # update change method count from small amount to large amount
            for small_amount in range(cur_coin, amount+1):
               
                # current small amount can make changed with current coin
                dp[small_amount] += dp[small_amount - cur_coin]

        return dp[amount]

用已知 Coin Change II的演算法，去解開組合數之和。

唯一的小差異就是原本只需要計算方法數，所以用int去累加方法數即可。

現在需要知道方法的具體組合情況，因此，我們用list [] 去記錄具體的組合數。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        
        dp = defaultdict(list)
        
        ## Base case:
        # $0 is reached by taking nothing
        dp[0] = [ [  ] ]
        
        coins = candidates
        
        ## General cases:
        # 請注意看，剛剛介紹的找零錢演算法就出現在這裡!
        for coin in coins:
            for amount in range(coin, target+1):
                
                # satisfy $amount from ($amount-$coin) + $coin
                for prev_coin_change in dp[ amount - coin ]:
                    dp[amount] += [ prev_coin_change + [coin] ]
        
        return dp[ target ]

幾乎九成像，對吧!

最長回文子序列 Longest Palindromic Subsequence

給定一個字串s，請計算s的最長回文子序列的長度。

這題常見的方法是用DP動態規劃配合回文框架去解，之前在專欄文章也解析過。

還有沒有別的解法呢? 其實有喔!

化簡到最長共同子序列 Longest Common Subsequence, aka LCS

仔細觀察，s的最長回文子序列。

這個動作就相當於，s 和 逆序的s 的最長共同子序列!

s 和 逆序的s 找共同序列，相當於共同子序列。

s 和 逆序的s 子序列如果有相同，那一定是回文的形式(因為彼此頭尾順序相反)。

那麼，這題最長回文子序列的問題，就被我們映射化簡到最長共同子序列LCS

只要計算s 和 逆序的s 的最長共同子序列的長度，就是最終答案。

原本已知的LCS的最長共同子序列演算法和解題程式碼

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
  			 # 請注意看，等等我們會用 最長共同子序列的演算法 去解開 最長回文子序列!
        dp = {}
        def LCS(i, j):

            if (i, j) in dp:
                return dp[i, j]

            if i == -1 or j == -1:
                dp[i, j]  = 0
                return 0
            
            elif text1[i] == text2[j]:
                dp[i, j] = LCS(i-1, j-1)+1
                return dp[i, j]

            else:
                dp[i, j] = max( LCS(i, j-1), LCS(i-1, j) )
                return dp[i, j]

        # ------------------------------
        return LCS( len(text1)-1, len(text2)-1 )

用已知 LCS最長共同子序列的演算法，去解開 最長回文子序列。

唯一的小差異就是傳入的參數，一個是原本的字串s，另一個是逆序的s。

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        
        # -------------------------------------------------
        # 請注意看，剛剛介紹的 最長共同子序列 就出現在這裡!
        dp = {}
        def LCS(i, j):

            if (i, j) in dp:
                return dp[i, j]

            if i == -1 or j == -1:
                dp[i, j]  = 0
                return 0
            
            elif text1[i] == text2[j]:
                dp[i, j] = LCS(i-1, j-1)+1
                return dp[i, j]

            else:
                dp[i, j] = max( LCS(i, j-1), LCS(i-1, j) )
                return dp[i, j]
            
        # -------------------------------------------------
        
        # Original s as text1
        text1 = s
        
        # Reversed s as text2
        text2 = s[::-1]
        
        # Longest palindromic subsequence of s = Longest common subsequence(s, s[::-1])
        return LCS( len(text1)-1, len(text2)-1 )        

幾乎九成像，對吧! 我們只要傳入 正序的s 和 逆序的s 即可。

合併k條已排序的Linked list Merge k Sorted Lists

給定k條已排序的串列，要求我們把k條串列合併成一條已排序的串列。

這題常見的方法是動態維護最小堆minHeap去解。

還有沒有別的解法呢? 其實有喔!

化簡到合併兩條已排序的串列 Merge Two Sorted Lists

仔細觀察，合併k條已排序的串列。

這個動作就相當於，前面k/2條的串列 和 後面k/2條的串列做合併!

前面和後面又可以如此反覆分割，一直到剩下一條串列或者空串列為止。

兩條已排序的串列合併我們已經會做了。

那麼，這題合併k條已排序串列的問題，就被我們映射化簡到合併兩條已排序串列。

只要不斷分割，倆倆先合併成一條，中間再不斷倆倆合併成一條，最後合併結果就是最終答案。

原本已知的合併兩條已排序串列的演算法和解題程式碼

class Solution:

    # 請注意看，等等我們會用 合併兩條已排序串列的演算法 去解開 合併k條已排序串列!
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        
        # List 1 is empty, then result is decided by List 2
        if not list1:
            return list2
        
        # List 2 is empty, then result is decided by List 1
        if not list2:
            return list1
        
        # General cases: compare node value, and update linkage
        if list1.val < list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
            
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

用已知 合併兩條已排序串列的演算法，去解開 合併k條已排序串列。

唯一的小差異就是多了k條之間，兩兩先分割再合併的動作。

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        #----------------------------------
        # 請注意看，剛剛介紹的 合併兩條已排序串列的演算法 就出現在這裡!
        def merge(l1, l2) -> ListNode:
            '''
            input: two sorted list l1, l2
            output: merged sorted list
            '''
            
            dummy_head = ListNode('#')
            cur = dummy_head
            
            while l1 and l2:
                if l1.val <= l2.val:
                    cur.next = l1
                    cur, l1 = cur.next, l1.next
                else:
                    cur.next = l2
                    cur, l2 = cur.next, l2.next
                    
            if l1:
                cur.next = l1
            else:
                cur.next = l2
                
            return dummy_head.next
        #----------------------------------
        
        if not lists:
            # base case:
            # empty list
            return None
        
        elif len(lists) == 1:
            # base case:
            # only one list
            return lists[0]
        
        # general case:
        # divide-and-conquer
        
        # divide:
        mid = len(lists)//2
        left = self.mergeKLists( lists[:mid] )
        right = self.mergeKLists( lists[mid:] )
        
        # conquer:
        return merge(left,right)

核心相同，只是多了兩兩分割和合併的外衣而已。

重點回顧: 化簡的關鍵步驟

找出新問題的核心是在問什麼?

觀察新問題和已知會解的問題、我們已經會的演算法，有沒有共通之處?

如果有，建立映射關係，把新問題化簡到已經會解的問題。

由已經會的演算法框架，構建出新問題的演算法與答案!

(通常只要很少量的修改即可，相當於搭橋、映射的動作)

結語

今天介紹了很靈活的演算法化簡技巧，
希望藉由思考流程、演算法化簡框架、經典例題的復現，
幫助讀者掌握這個重要的知識點。

我們下篇文章再見囉!