一魚多吃 用費式數列的DP模型來解 爬樓梯Climbing Stairs_Leetcode #70

小松鼠-avatar-img
發佈於演算法題目解析 個房間
更新於 發佈於 閱讀時間約 5 分鐘
raw-image

這題乍看之下是新題目,但仔細一想,其實只是前面介紹過的費式數列的小變形而已,解題思想基本不變。


題目敘述

原文題目可以在這裡看到

題目說每次可以爬一階樓梯或兩階樓梯,問爬到n階的方法數是多少。

對應的詳解影片,搭配服用,效果更佳。

範例輸入輸出如下:

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

複習再複習,Dynamic programming的解題框架可分為三大步驟

1. 定義DP狀態 [我在哪裡]

  1. 推導DP狀態轉移關係式(通則) [我從哪裡來] => [答案從哪裡推導而來]

3. 釐清DP初始狀態(也可以說是遞迴的終止條件) [第一步怎麼走,怎麼出發的]


這裡我們走過一遍DP解題框架,可分為三大步驟

1. 定義DP狀態 
[我在哪裡]

這題也滿直覺的,就令DP[n]為爬n階樓梯的方法數。


2. 定義DP狀態轉移關係式(通則)
[我從哪裡來] => [答案從哪裡推導而來]

題目說每次可以爬一階樓梯或兩階樓梯,也就是說

假如當下這層是第n階樓梯,那麼我們有兩種方式可以到達這裡:

一種是先到n-1階,接著再爬一階樓梯,那麼我們就到了第n階。

另一種是先到n-2階,接著再爬兩階樓梯,那麼我們就到了第n階。

用遞迴關係式表示就是

DP[n] = DP[n-1]+ DP[n-2]

其中DP[n-1]這項代表含先到n-1階再爬一階的意思, 而

DP[n-2]這項代表含先到n-2階再爬兩階的意思。

如下圖所示

raw-image

3. 釐清初始狀態(終止條件)
[第一步怎麼走,怎麼出發的]

比較敏銳的同學,可以發現,這條遞迴式和大家熟知的費式數列相同。

對的,就是f(n) = f(n-1) + f(n-2)的形式。

唯一的小差別初始條件不同而已。

爬0階樓梯有幾種方式?只有一種,就是什麼都沒做,沒有爬任何一階階梯。

DP[0] = 1

爬1階樓梯有幾種方式?只有一種,就是從0階往上爬一階就到第1階樓梯。

DP[1] = 1

更高層的2階, 3階…等還需要初始化嗎? 不用了,因為我們已經可以從遞回式DP[n] = DP[n-1] + DP[n-2] 計算出來。


到這裡,已經填滿解題框架的所有內容,接著我們把它轉成程式碼,

這裡以Python作為示範


程式碼 Top - down DP

class Solution:
 def climbStairs(self, n: int) -> int:
  
  # DP table
  # key: floor
  # value: method count to climb

  ## Base case
  table = {
     0: 1,
     1: 1
    }

  def dp( n: int) -> int:

   # look-up table
   if n in table:
    return table[n]

   ## General case
   table[n] = dp(n-1) + dp(n-2)
   return table[n]
   
  # ----------------------------------
  return dp(n)

程式碼 Bottom-up DP

class Solution:

 def climbStairs(self, n: int) -> int:

  # DP table
  # key: floor
  # value: method count to climb
  table = [1 for _ in range(n+1)]
  
  ## General case
  for i in range(2, n+1):
   table[i] = table[i-1] + table[i-2]
  
  return table[n]

複雜度分析

時間複雜度:O(n)

從n階樓梯降階到1階,每階樓梯的方法數可以在O(1)時間內計算完成。

空間複雜度:O(n)

DP table和遞迴呼叫深度皆為O(n)


學完這題的同學,記得去複習 DP動態規劃 深入淺出 以Fibonacci Number 費式數列 為例 這題喔,其實兩者背後的DP框架和觀念都是相通的喔!


下一篇: 活用DP: 泰伯納西數列的第n項 Leetcode #1137_精選75題


Reference:

[1] DP動態規劃 深入淺出 以Fibonacci Number 費式數列 為例|方格子 vocus

留言
avatar-img
留言分享你的想法!
小松鼠-avatar-img
發文者
2024/06/06
DP特訓班目錄 與 推薦的DP學習路徑 (持續更新中)提及了這篇文章,趕快過去看看吧!
avatar-img
小松鼠的演算法樂園
95會員
427內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
2024/09/13
給定一個整數陣列arr,和一串區間XOR請求queries。 請計算queries所請求的區間XOR值,並且以陣列的形式返回答案。
Thumbnail
2024/09/13
給定一個整數陣列arr,和一串區間XOR請求queries。 請計算queries所請求的區間XOR值,並且以陣列的形式返回答案。
Thumbnail
2024/08/27
Path with Maximum Probability 題目給定一個無向圖(雙向移動皆可), 提供每條邊的起終點,和每條邊對應的通過時的成功機率。 請問從起點start走到終點end的最高成功機率是多少? 如果完全沒有路徑可以抵達,則返回0。
Thumbnail
2024/08/27
Path with Maximum Probability 題目給定一個無向圖(雙向移動皆可), 提供每條邊的起終點,和每條邊對應的通過時的成功機率。 請問從起點start走到終點end的最高成功機率是多少? 如果完全沒有路徑可以抵達,則返回0。
Thumbnail
2024/08/21
題目敘述 664. Strange Printer 有一台奇怪的印表機, 每次操作只能連續印同樣的字母,但是列印的長度可以自由控制。 而且,印刷的時候,可以蓋過去舊的字元。 (這邊當然不合常理,讀者可以理解成塗了立可帶再蓋過去的情境) 給定一個輸入字串s,請問最少需要幾次操作,才能印出字串s?
Thumbnail
2024/08/21
題目敘述 664. Strange Printer 有一台奇怪的印表機, 每次操作只能連續印同樣的字母,但是列印的長度可以自由控制。 而且,印刷的時候,可以蓋過去舊的字元。 (這邊當然不合常理,讀者可以理解成塗了立可帶再蓋過去的情境) 給定一個輸入字串s,請問最少需要幾次操作,才能印出字串s?
Thumbnail
看更多
你可能也想看
Thumbnail
「欸!這是在哪裡買的?求連結 🥺」 誰叫你太有品味,一發就讓大家跟著剁手手? 讓你回購再回購的生活好物,是時候該介紹出場了吧! 「開箱你的美好生活」現正召喚各路好物的開箱使者 🤩
Thumbnail
「欸!這是在哪裡買的?求連結 🥺」 誰叫你太有品味,一發就讓大家跟著剁手手? 讓你回購再回購的生活好物,是時候該介紹出場了吧! 「開箱你的美好生活」現正召喚各路好物的開箱使者 🤩
Thumbnail
介紹朋友新開的蝦皮選物店『10樓2選物店』,並分享方格子與蝦皮合作的分潤計畫,註冊流程簡單,0成本、無綁約,推薦給想增加收入的讀者。
Thumbnail
介紹朋友新開的蝦皮選物店『10樓2選物店』,並分享方格子與蝦皮合作的分潤計畫,註冊流程簡單,0成本、無綁約,推薦給想增加收入的讀者。
Thumbnail
題目敘述 題目會給我們一個輸入陣列nums,每個元素值代表那個格子點可以跳躍的最大長度。 題目保證始從最左邊的格子點出發開始跳,一定可以成功抵達終點,請問最少跳躍次數是說少? 題目的原文敘述 測試範例 Example 1: Input: nums = [2,3,1,1,4] Outp
Thumbnail
題目敘述 題目會給我們一個輸入陣列nums,每個元素值代表那個格子點可以跳躍的最大長度。 題目保證始從最左邊的格子點出發開始跳,一定可以成功抵達終點,請問最少跳躍次數是說少? 題目的原文敘述 測試範例 Example 1: Input: nums = [2,3,1,1,4] Outp
Thumbnail
題目敘述 題目給定我們一顆二元樹的根節點,要求我們計算出從根節點到葉子節點的偽回文路徑路徑有幾條? 偽回文路徑路徑 的定義: 路徑經過重新排列之後,可以形成回文Palindrome,也就是頭尾鏡像對稱。 ​ 例如: 1 -> 3 -> 3 重新排列之後,可以形成 3 -> 1 -> 3
Thumbnail
題目敘述 題目給定我們一顆二元樹的根節點,要求我們計算出從根節點到葉子節點的偽回文路徑路徑有幾條? 偽回文路徑路徑 的定義: 路徑經過重新排列之後,可以形成回文Palindrome,也就是頭尾鏡像對稱。 ​ 例如: 1 -> 3 -> 3 重新排列之後,可以形成 3 -> 1 -> 3
Thumbnail
題目敘述 題目會給我們一個二維陣列matrix,分別代表每個格子的成本,請問我們從最頂端到底部的下墜路徑的最小成本總和是多少? 每次下墜到下一排的時候,可以有三種選擇: 1.往左下角移動。 2.往正下方移動。 3.往右下角移動。 題目的原文敘述 測試範例 Example 1:
Thumbnail
題目敘述 題目會給我們一個二維陣列matrix,分別代表每個格子的成本,請問我們從最頂端到底部的下墜路徑的最小成本總和是多少? 每次下墜到下一排的時候,可以有三種選擇: 1.往左下角移動。 2.往正下方移動。 3.往右下角移動。 題目的原文敘述 測試範例 Example 1:
Thumbnail
題目敘述 題目會告訴我們一組英文和數字之間的轉換編碼規則,還有一個輸入字串s,問我總共有多少合法的解碼方式? 要特別留意,輸入字串可能包含有leading zero,導致無法解碼。 轉換規則如下: A <-> 1 B <-> 2 C <-> 3 ... Z <-> 26 詳細的題
Thumbnail
題目敘述 題目會告訴我們一組英文和數字之間的轉換編碼規則,還有一個輸入字串s,問我總共有多少合法的解碼方式? 要特別留意,輸入字串可能包含有leading zero,導致無法解碼。 轉換規則如下: A <-> 1 B <-> 2 C <-> 3 ... Z <-> 26 詳細的題
Thumbnail
題目敘述 題目會給我們一個不規則排列的二維陣列,要求我們列出從起點出發,走次對角線,由左下到右上逐層拜訪的路徑。
Thumbnail
題目敘述 題目會給我們一個不規則排列的二維陣列,要求我們列出從起點出發,走次對角線,由左下到右上逐層拜訪的路徑。
Thumbnail
題目會給一個輸入陣列,裡面的數字分別代表每個index對應到的高度,要求我們計算山峰與低谷的數目,總共有多少個。 山峰 Hill: 比最靠近高度不相同的兩個鄰居的高度還要高。 低谷 Valley:比最靠近高度不相同的兩個鄰居的高度還要低。
Thumbnail
題目會給一個輸入陣列,裡面的數字分別代表每個index對應到的高度,要求我們計算山峰與低谷的數目,總共有多少個。 山峰 Hill: 比最靠近高度不相同的兩個鄰居的高度還要高。 低谷 Valley:比最靠近高度不相同的兩個鄰居的高度還要低。
Thumbnail
題目會給定一個2D 二維的矩陣,矩陣內的元素值代表對應的高度,要求我們找出相對最高點,也就是(大樓)高度大於N4 東、南、西、北 四個鄰居的索引值。 題目保證矩陣內相鄰的元素值都不相同,也又是相鄰的兩兩相比較,一定有一個比較高,有一個比較矮。
Thumbnail
題目會給定一個2D 二維的矩陣,矩陣內的元素值代表對應的高度,要求我們找出相對最高點,也就是(大樓)高度大於N4 東、南、西、北 四個鄰居的索引值。 題目保證矩陣內相鄰的元素值都不相同,也又是相鄰的兩兩相比較,一定有一個比較高,有一個比較矮。
Thumbnail
爬到頂樓的最小成本, 這題算是前面那題Climbing stairs的變形題,有點小變化, 但是稍微想一下還是能推導出來,算是很好的一維動態規劃1D DP練習題。
Thumbnail
爬到頂樓的最小成本, 這題算是前面那題Climbing stairs的變形題,有點小變化, 但是稍微想一下還是能推導出來,算是很好的一維動態規劃1D DP練習題。
Thumbnail
這題乍看之下是新題目,但仔細一想, 其實只是前面介紹過的費式數列的小變形而已,解題思想基本不變。 題目說每次可以爬一階樓梯或兩階樓梯,問爬到n階的方法數是多少。
Thumbnail
這題乍看之下是新題目,但仔細一想, 其實只是前面介紹過的費式數列的小變形而已,解題思想基本不變。 題目說每次可以爬一階樓梯或兩階樓梯,問爬到n階的方法數是多少。
Thumbnail
題目會給定給我們一顆二元樹的根結點, 要求我們輸出上下顛倒的Level-order traversal的拜訪結果。
Thumbnail
題目會給定給我們一顆二元樹的根結點, 要求我們輸出上下顛倒的Level-order traversal的拜訪結果。
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News