化簡無所不在 用LCS的DP模型解Uncrossed Lines_Leetcode #1035

閱讀時間約 8 分鐘

題目敘述 Uncrossed Lines

給定兩個輸入整數陣列,若在兩個陣列遇到相同的數字可以連成一線,但是有規定連線不可和別的連線有交叉

請問最多可以形成幾條連線?


測試範例

Example 1:

raw-image


Input: nums1 = [1,4,2], nums2 = [1,2,4]
Output: 2
Explanation: We can draw 2 uncrossed lines as in the diagram.
We cannot draw 3 uncrossed lines, because the line from nums1[1] = 4 to nums2[2] = 4 will intersect the line from nums1[2]=2 to nums2[1]=2.

Example 2:

Input: nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
Output: 3

Example 3:

Input: nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
Output: 2

約束條件

Constraints:

  • 1 <= nums1.length, nums2.length <= 500

輸入陣列的長度都介於1~500之間。

  • 1 <= nums1[i], nums2[j] <= 2000

陣列裡的每個數字都介於1~2000之間。


觀察

連線的規則是:

  1. 兩個陣列要遇到相同的數字,可以建立一條新連線。
  2. 新的連線不能和別的連線交叉


目標:
最多的連線數目


想要連線數目越多越好,
代表兩個陣列的相同的數字越多越好,而且不能和別的連線交叉。


...似曾相似...對吧! 其實在前面就有看過類似的限制條件。

Longest Common Subsequence這一題,題目說的是最長共同子序列。

一般化地說,兩個陣列的相同的字元越多越好,而且不能和別的連線交叉


到這邊,我們已經發現,其實這兩題具有同樣的形式,只是換句話說重新包裝而已。

差別只是在於type型別,一個是字串,一個是整數Integer,僅此差別而已。

但是子序列延伸(或者說製造連線)的方式完全相同。

因此,我們可以透過演算法化簡的技巧,把這題映射到原本已經學會的
Longest Common Subsequence的DP模型來解開。


演算法 化簡到LCS最長共同子序列的DP模型

1. 定義DP狀態

DP[i,j]代表陣列nums1[0~i], nums2[0~j]的最多連線數目。

最終所求是什麼?

自然就是兩個陣列的最多連線數目 = DP[ len(nums1)-1, len(nums2)-1]


2. 推導DP狀態轉移關係式

如果nums1[i] == nums2[j]

代表現在數字相同,可以多建立一條連線

總連線數 = 剩餘的子陣列連線數目 + 1

DP[i, j] = DP[i-1, j-1] + 1


如果nums1[i] != nums2[j]

代表現在數字不同,無法多建立新連線

總連線數 = 去掉當下的數字,剩餘的子陣列連線數目

DP[i, j] = Max{ DP[i-1, j], DP[i, j-1] }


3.釐清DP初始狀態

最小規模的題目是什麼?

其實就是對比到空陣列的時候

這時候,肯定沒有相同的數字,連線數目=0

DP[i, j] = 0 if i == -1

DP[i, j] = 0 if j == -1


程式碼 化簡到LCS最長共同子序列的DP模型

class Solution:
def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:

# key: index pair
# value: max counting of connection
dp_table = {}

def connect( idx_a, idx_b ):

if (idx_a, idx_b) in dp_table:
return dp_table[(idx_a, idx_b)]


if idx_a == -1 or idx_b == -1:
# Any list compared to empty list give no uncrossed line
dp_table[(idx_a, idx_b)] = 0
return 0

elif A[idx_a] == B[idx_b]:

dp_table[(idx_a, idx_b)] = connect(idx_a-1, idx_b-1) + 1
return dp_table[(idx_a, idx_b)]
else:
dp_table[(idx_a, idx_b)] = max( connect(idx_a-1, idx_b), connect(idx_a, idx_b-1))
return dp_table[(idx_a, idx_b)]

# --------------------------------------------
return connect( len(A)-1, len(B)-1 )

等價的Bottom up DP程式碼

class Solution:
def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:

# padding one dummy -1 to represent empty list
A = [ -1 ] + A
B = [ -1 ] + B

h, w = len(A), len(B)
dp_table = [ [ 0 for _ in range(w) ] for _ in range(h) ]



for y in range(1, h):
for x in range(1, w):

if A[y] == B[x]:
# current number is matched, add one more uncrossed line
dp_table[y][x] = dp_table[y-1][x-1] + 1

else:
# cuurent number is not matched, backtracking to find maximal uncrossed line
dp_table[y][x] = max( dp_table[y][x-1], dp_table[y-1][x] )


return dp_table[-1][-1]

複雜度分析

時間複雜度: O( m * n )

考慮到索引移動配對,總共有O(m*n)個狀態,

每個狀態可以在O(1)內計算完成。


空間複雜度: O( m*n )

DP table 所需空間為 O( m*n )。


關鍵知識點

題意和限制條件推理得知,其實這題和Longest Common Subsequence本質上是同一題,只是換湯不換藥重新包裝過,可以相同物建立不交叉的連線的DP模型來解開。

強烈建議同時複習Longest Common Subsequence這一題,

熟悉DP演算法框架和掌握演算法化簡的技巧。


Refernce

[1] Uncrossed Lines - LeetCode

58會員
345內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!
你可能也想看
迎新活動「方格新手村」:新格友註冊加入方格子,知名日料吃到飽餐券送給你! 👉 還不是 vocus 的會員嗎?點此註冊,參與新手村活動 👈 近期站上也出現了不少新格友,為了歡迎各位的加入,「方格新手村」隨之登場! 即日起,只要是新註冊帳號於活動期間內發佈 3 則文章,就有機會抽獎獲得知名日料吃到飽餐券。原格友也可以一起同樂,我們準備了小任
Thumbnail
2024-06-21
95
順利佮人講話是無簡單的代誌我的小弟中風一年外,是出血型中風,傷著的是倒爿 pîng的頭腦,邏輯、語言等等,逐禮拜去病院做復健幾若擺,我一禮拜去恁兜一擺,佮伊同齊做一寡仔認知、講話、唸字、寫字的練習。   我想著的代誌攏共試看覓,譬喻講:自1唸到100、奇數、雙數,數字會曉加做伙無?會曉算豆仔無?三角形、圓形……會曉認無?
Thumbnail
2024-05-05
6
🍀【臼井聖火靈氣學員的上課心得-71】在靈氣點化中遇見天使的自己,感覺一切『無所畏懼的安定』悸動💗🍀🍀🍀fumi老師:❤️❤️❤ 🥰🥰🥰靈氣大師階的課程點化,是一開始會先探尋自己的內在世界,當同學看到「小王子」出現,是自己內在的形象展現,看得出來是一位充滿著赤子之心、保有童稚的溫暖療癒師。 💞💞💞在邁進靈氣大師的階段時,會是一個重新整理、重新整合自己的最棒的時機,你會看到自
Thumbnail
2024-01-26
5
節能減碳,打造無紙化綠色企業2020年開始,因新冠疫情肆虐,導致人心惶惶,自然界也沒有平靜過......。氣候變遷、海洋危機、森林大火、高溫乾旱等問題遍及全球各地,去年台灣更遭逢半世紀以來最慘的水荒!很明顯全球暖化引起的極端氣候已近在眼前。 自從歐洲工業革命以來,人類的工業活動大量燃燒煤炭、石油等化石燃料,而二氧化碳排放量也從
Thumbnail
2023-01-03
7
昨晚油價的瞬間變化以及最近的台積電,新聞製造無所不在。昨天(11月21日)的過程是這樣,原本平緩的走勢,突然傳出了下面的新聞: 美媒稱OPEC考慮下月宣布增產 遭沙烏地否認 出現增產50萬桶的新聞後,油價急殺了5美元,然後又出現了沙國澄清否認的新聞,走勢就急彈回到原本平緩的位置。
Thumbnail
2022-11-22
85
【簡筆畫 #3】中秋佳節 愉快,萬里無雲鏡九州,最團圓夜 本次作品,是以中秋節和嫦娥為設計主軸,再搭配一些可愛的人物、動物來構圖,穿插一些小飾品,就可以構出一個具有個人風格的圖畫啦~ 有興趣的朋友也可以拿起自己的畫筆,就直接畫上去了,別想太多!
Thumbnail
斷捨離不難!丹寧風、運動風、甜美風,只要搭上這件T恤就能無限變化新造型,極簡生活也能享受穿搭!妳是否也有過這種情形? 每到一個季節就會有源源不絕新單品出現,逛街看到就心動地打包帶回家,但回到家後開始面對炸滿出來的衣櫃,亦或是趕時間想搭配但困擾無法快速辨別衣服,想實施衣櫃斷捨離但每件都是心頭肉下不了手,讓總總因素困擾著...然後就又過了一個季節...。
Thumbnail
2022-03-30
0
國內疫情穩定 陳時中:無規畫9/7後降級 評估開放運動場所淋浴間中央流行疫情指揮中心日前宣布,8月24日至9月6日國內維持第2級疫情警戒,由於新冠肺炎本土疫情近日穩定,外界關注9月7日後是否有升降級考量。指揮中心指揮官陳時中今天透露,9月7日後沒有降級打算,但正在評估開放運動場所淋浴間及增加雙鐵運量。 中央流行疫情指揮中心下午召開疫情記者會,指揮中心指揮官陳時中
Thumbnail
2021-08-30
2
無法下班的接案人生30/接案人生是一件簡化生活的事!很多人會說「在家工作會分不清楚什麼時候在工作」這句話只對了一半。另一半的答案要讓接案的人來答:「接案的人沒有上班和下班的時間,生活裡有工作,而工作也是生活的一部分!」
Thumbnail
2021-05-03
7
校慶減塑強化版—師大附中「無塑」園遊會 園遊會,幾乎是每個台灣高中生生涯中難忘的一塊。當我們從課堂中學習了經濟模型、科技運用,從社團中學會了統籌規劃、分工合作,終於能在園遊會上,將所學、所思、所想付諸行動,相信對所有人都是一段難忘的回憶。 舉辦無塑園遊會(不是減塑而是「無塑」)對於任何高中都是一大難題,更別談在校生將近三千人的師大附中了
Thumbnail
迎新活動「方格新手村」:新格友註冊加入方格子,知名日料吃到飽餐券送給你! 👉 還不是 vocus 的會員嗎?點此註冊,參與新手村活動 👈 近期站上也出現了不少新格友,為了歡迎各位的加入,「方格新手村」隨之登場! 即日起,只要是新註冊帳號於活動期間內發佈 3 則文章,就有機會抽獎獲得知名日料吃到飽餐券。原格友也可以一起同樂,我們準備了小任
Thumbnail
2024-06-21
95
順利佮人講話是無簡單的代誌我的小弟中風一年外,是出血型中風,傷著的是倒爿 pîng的頭腦,邏輯、語言等等,逐禮拜去病院做復健幾若擺,我一禮拜去恁兜一擺,佮伊同齊做一寡仔認知、講話、唸字、寫字的練習。   我想著的代誌攏共試看覓,譬喻講:自1唸到100、奇數、雙數,數字會曉加做伙無?會曉算豆仔無?三角形、圓形……會曉認無?
Thumbnail
2024-05-05
6
🍀【臼井聖火靈氣學員的上課心得-71】在靈氣點化中遇見天使的自己,感覺一切『無所畏懼的安定』悸動💗🍀🍀🍀fumi老師:❤️❤️❤ 🥰🥰🥰靈氣大師階的課程點化,是一開始會先探尋自己的內在世界,當同學看到「小王子」出現,是自己內在的形象展現,看得出來是一位充滿著赤子之心、保有童稚的溫暖療癒師。 💞💞💞在邁進靈氣大師的階段時,會是一個重新整理、重新整合自己的最棒的時機,你會看到自
Thumbnail
2024-01-26
5
節能減碳,打造無紙化綠色企業2020年開始,因新冠疫情肆虐,導致人心惶惶,自然界也沒有平靜過......。氣候變遷、海洋危機、森林大火、高溫乾旱等問題遍及全球各地,去年台灣更遭逢半世紀以來最慘的水荒!很明顯全球暖化引起的極端氣候已近在眼前。 自從歐洲工業革命以來,人類的工業活動大量燃燒煤炭、石油等化石燃料,而二氧化碳排放量也從
Thumbnail
2023-01-03
7
昨晚油價的瞬間變化以及最近的台積電,新聞製造無所不在。昨天(11月21日)的過程是這樣,原本平緩的走勢,突然傳出了下面的新聞: 美媒稱OPEC考慮下月宣布增產 遭沙烏地否認 出現增產50萬桶的新聞後,油價急殺了5美元,然後又出現了沙國澄清否認的新聞,走勢就急彈回到原本平緩的位置。
Thumbnail
2022-11-22
85
【簡筆畫 #3】中秋佳節 愉快,萬里無雲鏡九州,最團圓夜 本次作品,是以中秋節和嫦娥為設計主軸,再搭配一些可愛的人物、動物來構圖,穿插一些小飾品,就可以構出一個具有個人風格的圖畫啦~ 有興趣的朋友也可以拿起自己的畫筆,就直接畫上去了,別想太多!
Thumbnail
斷捨離不難!丹寧風、運動風、甜美風,只要搭上這件T恤就能無限變化新造型,極簡生活也能享受穿搭!妳是否也有過這種情形? 每到一個季節就會有源源不絕新單品出現,逛街看到就心動地打包帶回家,但回到家後開始面對炸滿出來的衣櫃,亦或是趕時間想搭配但困擾無法快速辨別衣服,想實施衣櫃斷捨離但每件都是心頭肉下不了手,讓總總因素困擾著...然後就又過了一個季節...。
Thumbnail
2022-03-30
0
國內疫情穩定 陳時中:無規畫9/7後降級 評估開放運動場所淋浴間中央流行疫情指揮中心日前宣布,8月24日至9月6日國內維持第2級疫情警戒,由於新冠肺炎本土疫情近日穩定,外界關注9月7日後是否有升降級考量。指揮中心指揮官陳時中今天透露,9月7日後沒有降級打算,但正在評估開放運動場所淋浴間及增加雙鐵運量。 中央流行疫情指揮中心下午召開疫情記者會,指揮中心指揮官陳時中
Thumbnail
2021-08-30
2
無法下班的接案人生30/接案人生是一件簡化生活的事!很多人會說「在家工作會分不清楚什麼時候在工作」這句話只對了一半。另一半的答案要讓接案的人來答:「接案的人沒有上班和下班的時間,生活裡有工作,而工作也是生活的一部分!」
Thumbnail
2021-05-03
7
校慶減塑強化版—師大附中「無塑」園遊會 園遊會,幾乎是每個台灣高中生生涯中難忘的一塊。當我們從課堂中學習了經濟模型、科技運用,從社團中學會了統籌規劃、分工合作,終於能在園遊會上,將所學、所思、所想付諸行動,相信對所有人都是一段難忘的回憶。 舉辦無塑園遊會(不是減塑而是「無塑」)對於任何高中都是一大難題,更別談在校生將近三千人的師大附中了
Thumbnail