付費限定
一魚多吃 用費式數列的模型來解 Min Cost Climbing Stairs_Leetcode #746_精選75題
閱讀時間約 8 分鐘
這題算是前面那題Climbing stairs的變形題，有點小變化，但是稍微想一下還是能推導出來，算是很好的一維動態規劃1D DP練習題。
回憶一下題過的DP解題框架與三大步驟
1. 定義狀態 [我在哪裡]
2. 定義狀態轉移關係式(通則) [我從哪裡來] => [答案從哪裡推導而來]
3. 釐清初始狀態(也可以說是遞迴的終止條件) [第一步怎麼走，怎麼出發的]
題目敘述
詳細的原文題目可以在這裡看到 Min Cost Climbing Stairs
題目說每次可以爬一階樓梯或兩階樓梯，爬到第i層階梯時，會有一個附帶成本cost[i]
題目問爬到終點(最高階樓梯)的最小成本是多少。
測試範例:
Example 1:
Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.
Example 2:
Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.
這裡我們走過一遍DP解題框架
1. 定義DP狀態
[我在哪裡]
這題滿直覺的，就令DP[n]為爬n階樓梯的最小成本。
最後所求就是min( DP[n-1], DP[n-2] )，因為最後一次要嘛踩一階可以到最後一層，要嘛踩兩階可以到最後一層。
2. 定義DP狀態轉移關係式(通則)
[我從哪裡來] => [答案從哪裡推導而來]
題目說每次可以爬一階樓梯或兩階樓梯，也就是說
假如當下這層是第i階樓梯，那麼我們有兩種方式可以到達這裡:
一種是先到i-1階，接著再爬一階樓梯，那麼我們就到了第n階。
另一種是先到i-2階，接著再爬兩階樓梯，那麼我們就到了第n階。
題目要求我們計算最小成本，所以是取min最小值。
然後，別忘了，抵達第i層階梯時，本身有一個附帶成本cost[i]
以行動支持創作者！付費即可解鎖
本篇內容共 3314 字、2
則留言，僅發佈於Leetcode精選75題 解析+統整、DP動態規劃 特訓班你目前無法檢視以下內容，可能因為尚未登入，或沒有該房間的查看權限。
88會員
425內容數
由有業界實戰經驗的演算法工程師，
手把手教你建立解題的框架，
一步步寫出高效、清晰易懂的解題答案。
著重在讓讀者啟發思考、理解演算法，熟悉常見的演算法模板。
深入淺出地介紹題目背後所使用的演算法意義，融會貫通演算法與資料結構的應用。
在幾個經典的題目融入一道題目的多種解法，或者同一招解不同的題目，擴展廣度，並加深印象。
留言0
查看全部
你可能也想看
Google News 追蹤
這個秋，Chill 嗨嗨！穿搭美美去賞楓，裝備款款去露營⋯⋯你的秋天怎麼過？秋日 To Do List 等你分享！
秋季全站徵文，我們準備了五個創作主題，參賽還有機會獲得「火烤兩用鍋」，一起來看看如何參加吧～
11/20日NVDA即將公布最新一期的財報, 今天Sell Side的分析師, 開始調高目標價, 市場的股價也開始反應, 未來一週NVDA將重新回到美股市場的焦點, 今天我們要分析NVDA Sell Side怎麼看待這次NVDA的財報預測, 以及實際上Buy Side的倉位及操作, 從
Hi 大家好，我是Ethan😊
相近大家都知道保濕是皮膚保養中最基本，也是最重要的一步。無論是在畫室裡長時間對著畫布，還是在旅途中面對各種氣候變化，保持皮膚的水分平衡對我來說至關重要。保濕化妝水不僅能迅速為皮膚補水，還能提升後續保養品的吸收效率。
曾經，我的保養程序簡單到只包括清潔和隨意上乳液
子集合生成是一道經典的組合類上機考和面試題目。本篇文章介紹多個不同的解決方案，以及相關演算法框架。主要目標是給定n個相異的元素，產生所有的子集合。
題目敘述
給定兩個字串word1和word2，每次操作時，可以有三個選項
插入一個字元
刪除一個字元
替換一個字元
請問把word1轉換成word2的最小操作次數是多少？
題目的原文敘述
約束條件
Constraints:
0 <= word1.length, word2.le
題目敘述
題目會給我們兩種無限量供應的骨牌Domino 和 Tromino，形狀分別如下
題目的輸入會有一個參數n。
可以任意旋轉方向進行拼接，請問最後拼成 2 x n 長方形區域的方法數有幾種?
例如 n = 3 時，拼成2 x 3 的長方形區域有五種方法。
題目的原文敘述
題目敘述
題目會給定我們一個n值，要求我們列出從0 ~ n 之間，每個整數有幾個bit1，以陣列的形式返回答案。
例如n=3時
因為
0 = 0b 0
1 = 0b 1
2 = 0b 10
3 = 0b 11
輸出答案為[0, 1, 1, 2]
題目的原文敘述
測試範例
E
題目敘述
題目會給定一個字串陣列arr最為輸入，我們可以任意選擇一組不包含重複字元的陣列子序列，將字串進行串接，成為字串s，請問字串s的最大長度是多少?
例如:
arr=["dog","cow","cat"]
我們可以選擇"dog", "cat"進行串接，得到的字串s="dogcat"，s的
關於一主多奴，奴寵部份也該注意什麼？
要完全站在奴寵位置思考，還是有點難😅
1.妳能夠在理解之後，打心底接受這樣的關係嗎？
這邊說的接受，不是不停洗腦自己去接受這樣的關係，而是真的能夠接受這樣的關係，理解跟接受是兩回事。
2.妳曾想過想要怎樣的同伴嗎？
因為有時候，可能是妳和她相處的時間
關於一主多奴，無論是主、奴哪方都需要注意的事項。
1.作為主人，你足夠坦誠嗎？
這邊指的坦誠，並不是指等你有了第一個奴一段時間，才突然坦承自己想要多收奴，而是一開始建立關係之前就必須告知讓奴方了解，這是義務，也是作為主人的責任。
在有第一位奴願意理解、接受之後，對後來遇到的第二位甚至往後幾位，
很多的時候，大家都會認為一些成功者，都是很聰明的。【其實不然】。
阿里巴巴的創辦人馬雲，算是一位特別傳奇人物。
其中馬雲高中畢業，參加第一次高考(大學入學考試)，大家應該不敢相信其中數學考了1分。
股票可以一魚多吃?
可以，我們熟知的股票，主要是做價差或領股息，但是您知道，還可以做什麼用途嗎?
假如我們不要把股票賣掉，所以不做價差，那麼股票就可以做以下用途。
說過上餘裕的生活，其實和「財富自由」沒有絕對關係⋯⋯時常覺得夢想和快樂是世上最快被放棄東西，無論是現實勒緊褲袋、或成就地位束縛，是說得頭頭是道卻毫無價值，總是第一個被捨棄⋯⋯
這個秋，Chill 嗨嗨！穿搭美美去賞楓，裝備款款去露營⋯⋯你的秋天怎麼過？秋日 To Do List 等你分享！
秋季全站徵文，我們準備了五個創作主題，參賽還有機會獲得「火烤兩用鍋」，一起來看看如何參加吧～
11/20日NVDA即將公布最新一期的財報, 今天Sell Side的分析師, 開始調高目標價, 市場的股價也開始反應, 未來一週NVDA將重新回到美股市場的焦點, 今天我們要分析NVDA Sell Side怎麼看待這次NVDA的財報預測, 以及實際上Buy Side的倉位及操作, 從
Hi 大家好，我是Ethan😊
相近大家都知道保濕是皮膚保養中最基本，也是最重要的一步。無論是在畫室裡長時間對著畫布，還是在旅途中面對各種氣候變化，保持皮膚的水分平衡對我來說至關重要。保濕化妝水不僅能迅速為皮膚補水，還能提升後續保養品的吸收效率。
曾經，我的保養程序簡單到只包括清潔和隨意上乳液
子集合生成是一道經典的組合類上機考和面試題目。本篇文章介紹多個不同的解決方案，以及相關演算法框架。主要目標是給定n個相異的元素，產生所有的子集合。
題目敘述
給定兩個字串word1和word2，每次操作時，可以有三個選項
插入一個字元
刪除一個字元
替換一個字元
請問把word1轉換成word2的最小操作次數是多少？
題目的原文敘述
約束條件
Constraints:
0 <= word1.length, word2.le
題目敘述
題目會給我們兩種無限量供應的骨牌Domino 和 Tromino，形狀分別如下
題目的輸入會有一個參數n。
可以任意旋轉方向進行拼接，請問最後拼成 2 x n 長方形區域的方法數有幾種?
例如 n = 3 時，拼成2 x 3 的長方形區域有五種方法。
題目的原文敘述
題目敘述
題目會給定我們一個n值，要求我們列出從0 ~ n 之間，每個整數有幾個bit1，以陣列的形式返回答案。
例如n=3時
因為
0 = 0b 0
1 = 0b 1
2 = 0b 10
3 = 0b 11
輸出答案為[0, 1, 1, 2]
題目的原文敘述
測試範例
E
題目敘述
題目會給定一個字串陣列arr最為輸入，我們可以任意選擇一組不包含重複字元的陣列子序列，將字串進行串接，成為字串s，請問字串s的最大長度是多少?
例如:
arr=["dog","cow","cat"]
我們可以選擇"dog", "cat"進行串接，得到的字串s="dogcat"，s的
關於一主多奴，奴寵部份也該注意什麼？
要完全站在奴寵位置思考，還是有點難😅
1.妳能夠在理解之後，打心底接受這樣的關係嗎？
這邊說的接受，不是不停洗腦自己去接受這樣的關係，而是真的能夠接受這樣的關係，理解跟接受是兩回事。
2.妳曾想過想要怎樣的同伴嗎？
因為有時候，可能是妳和她相處的時間
關於一主多奴，無論是主、奴哪方都需要注意的事項。
1.作為主人，你足夠坦誠嗎？
這邊指的坦誠，並不是指等你有了第一個奴一段時間，才突然坦承自己想要多收奴，而是一開始建立關係之前就必須告知讓奴方了解，這是義務，也是作為主人的責任。
在有第一位奴願意理解、接受之後，對後來遇到的第二位甚至往後幾位，
很多的時候，大家都會認為一些成功者，都是很聰明的。【其實不然】。
阿里巴巴的創辦人馬雲，算是一位特別傳奇人物。
其中馬雲高中畢業，參加第一次高考(大學入學考試)，大家應該不敢相信其中數學考了1分。
股票可以一魚多吃?
可以，我們熟知的股票，主要是做價差或領股息，但是您知道，還可以做什麼用途嗎?
假如我們不要把股票賣掉，所以不做價差，那麼股票就可以做以下用途。
說過上餘裕的生活，其實和「財富自由」沒有絕對關係⋯⋯時常覺得夢想和快樂是世上最快被放棄東西，無論是現實勒緊褲袋、或成就地位束縛，是說得頭頭是道卻毫無價值，總是第一個被捨棄⋯⋯