演算法映射化簡的核心觀念
在面對新題目的時候，除了重頭想一個新的演算法之外；
還有另一個方法，想看看有沒有核心觀念彼此相同的問題與演算法，
如果有，就可以把新的題目映射化簡到已知解法的問題，用已知的演算法去解開。
接著，我們會介紹幾個範例，並且使用映射化簡的技巧來解題，透過化簡框架的復現，幫助讀者掌握這個知識點。
組合數之和 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)
核心相同，只是多了兩兩分割和合併的外衣而已。
重點回顧: 化簡的關鍵步驟
找出新問題的核心是在問什麼?
觀察新問題和已知會解的問題、我們已經會的演算法，有沒有共通之處?
如果有，建立映射關係，把新問題化簡到已經會解的問題。
由已經會的演算法框架，構建出新問題的演算法與答案!
(通常只要很少量的修改即可，相當於搭橋、映射的動作)
結語
今天介紹了很靈活的演算法化簡技巧，
希望藉由思考流程、演算法化簡框架、經典例題的復現，
幫助讀者掌握這個重要的知識點。
我們下篇文章再見囉!
