化簡無所不在 用學過的DP模型解House Robbery II_Leetcode #213

閱讀時間約 6 分鐘

題目敘述 House Robber II

題目會給我們一個nums陣列,分別代表每棟房屋的價值,也就是房屋內有的現金數量。

題目敘述給的情境是假想盜賊要偷東西,限制是相鄰的兩棟房屋不能一起偷,只能選擇其中一棟,否則就會觸發警報器。第一棟和最後一棟也被視為相鄰

請問盜賊可以得到最大成果是多少?


測試範例

Example 1:

Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

取中間那棟3得到最大價值。​

Example 2:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

取第一棟1和第三棟3,總共得到4為最大價值。​

Example 3:

Input: nums = [1,2,3]
Output: 3

取最後一洞3得到最大價值。

約束條件

Constraints:

  • 1 <= nums.length <= 100

輸入陣列長度介於1~100之間。

  • 0 <= nums[i] <= 1000

陣列元素(每棟房屋的價值)介於0~1000之間。


觀察 

其實這題和House Robbery I 幾乎一樣,只是多了一個頭尾視為相鄰的限制條件。

(也就是說,第一棟和最後一棟是互斥的,不可以同時選。

換句話說,我們知道有兩種情況:

如果考慮了第一棟,那麼最後一棟不可能被選進來,考慮區間的index相當於0~n-2
如果考慮最後一棟,那麼第一棟不可能被選進來,考慮區間的index相當於1~n-1

目標同樣是掠奪的最大值,所以

掠奪的最大值

= Max{ 第一種情況,第二種情況}

=Max{ 考慮第一棟, 考慮最後一棟}

= Max{ House Robbery I [0~n-2], House Robbery I [1~n-1] }



演算法 化簡到House Robbery I 的DP模型

承接觀察點的思考,

原本的House Robbery II在經過討論和觀察後,其實就只有兩種情況,


掠奪的最大值

= Max{ 第一種情況,第二種情況}

=Max{ 考慮第一棟, 考慮最後一棟}

= Max{ House Robbery I 房屋區間[0~n-2], House Robbery I 房屋區間[1~n-1] }


對應的這兩種情況傳入原本我們已經學會的House Robbery I的演算法

取兩者之間的最大值,就是最終答案,也就是掠奪的最大值。


程式碼 化簡到House Robbery I 的DP模型

class Solution:
def rob(self, nums: List[int]) -> int:

def solve( arr ):

dp = {}
def consider( i ):
# look-up table
if i in dp:
return dp[i]

# base case
if i == 0:
dp[0] = arr[0]
return dp[0]

# base case
if i == 1:
dp[1] = max(arr[0], arr[1])
return dp[1]

# general case
take = arr[i] + consider(i-2)
skip = 0 + consider(i-1)

dp[i] = max( take, skip )
return dp[i]
# =======================================
return consider( i = len(arr)-1 )
# ----------------------------------------------------

if len(nums) == 1:
return nums[0]

return max( solve(nums[:len(nums)-1]), solve(nums[1:]) )


複雜度分析

時間複雜度:O( n )

一維DP,從第一棟房子逐步遞迴計算到最後一棟房子。


空間複雜度:O(n)

需要建立一張表格value_dp,所佔用空間為O(n)。


關鍵知識點


利用化簡的技巧,發現彼此結構相同,把這題化簡到已經會解的House Robbery I

一魚多吃 用DP解House Robbery 打家劫舍問題_Leetcode #198_Leetcode 精選75題解析


其實這題和House Robbery I 幾乎一樣,只是多了一個頭尾視為相鄰的限制條件。

(也就是說,第一棟和最後一棟是互斥的,不可以同時選。

換句話說,我們知道有兩種情況:

如果考慮了第一棟,那麼最後一棟不可能被選進來,考慮區間的index相當於0~n-2
如果考慮最後一棟,那麼第一棟不可能被選進來,考慮區間的index相當於1~n-1


目標同樣是掠奪的最大值,所以

掠奪的最大值

= Max{ 第一種情況,第二種情況}

=Max{ 考慮第一棟, 考慮最後一棟}

= Max{ House Robbery I [0~n-2], House Robbery I [1~n-1] }


Reference

[1] House Robber II - LeetCode

60會員
348內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!
你可能也想看
迎新活動「方格新手村」:新格友註冊加入方格子,知名日料吃到飽餐券送給你! 👉 還不是 vocus 的會員嗎?點此註冊,參與新手村活動 👈 近期站上也出現了不少新格友,為了歡迎各位的加入,「方格新手村」隨之登場! 即日起,只要是新註冊帳號於活動期間內發佈 3 則文章,就有機會抽獎獲得知名日料吃到飽餐券。原格友也可以一起同樂,我們準備了小任
Thumbnail
2024-06-21
100
川普當選,對台股是利多還是利空?川普在槍擊事件中所表現出來的英勇形象,讓他贏得美國總統大選幾乎已成定局。沒想到他隨口的一句話「台灣搶走美國的晶片生意,所以要付保護費」,就讓台積電在短短三天跌掉超過100 元,台股也跌掉1100點以上。台積電、台股會就此一路下跌嗎?未來該如何因應?  
Thumbnail
2024-07-20
67
金融科技與生活美學的融合 CUBE App實踐自我理想最近開啟了研究工作,也開始斜槓著手團購、行銷、洽談業務,慢慢想打造一條屬於自己的道路,而工作忙碌之虞,總忘記自己刷卡消費明細、信用卡繳費,還會忽略了最應該的投資理財,也常常在忙碌奔波中忘記信用卡優惠,國泰世華CUBE App給足了這些功能和服務。 日常生活與數位、科技形影不離,同時也拉近彼此距
Thumbnail
2024-07-11
22
順利佮人講話是無簡單的代誌我的小弟中風一年外,是出血型中風,傷著的是倒爿 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
100
川普當選,對台股是利多還是利空?川普在槍擊事件中所表現出來的英勇形象,讓他贏得美國總統大選幾乎已成定局。沒想到他隨口的一句話「台灣搶走美國的晶片生意,所以要付保護費」,就讓台積電在短短三天跌掉超過100 元,台股也跌掉1100點以上。台積電、台股會就此一路下跌嗎?未來該如何因應?  
Thumbnail
2024-07-20
67
金融科技與生活美學的融合 CUBE App實踐自我理想最近開啟了研究工作,也開始斜槓著手團購、行銷、洽談業務,慢慢想打造一條屬於自己的道路,而工作忙碌之虞,總忘記自己刷卡消費明細、信用卡繳費,還會忽略了最應該的投資理財,也常常在忙碌奔波中忘記信用卡優惠,國泰世華CUBE App給足了這些功能和服務。 日常生活與數位、科技形影不離,同時也拉近彼此距
Thumbnail
2024-07-11
22
順利佮人講話是無簡單的代誌我的小弟中風一年外,是出血型中風,傷著的是倒爿 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