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

一魚多吃 用費式數列的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
小松鼠的演算法樂園
95會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言
avatar-img
留言分享你的想法!
給定一個整數陣列arr,和一串區間XOR請求queries。 請計算queries所請求的區間XOR值,並且以陣列的形式返回答案。
Path with Maximum Probability 題目給定一個無向圖(雙向移動皆可), 提供每條邊的起終點,和每條邊對應的通過時的成功機率。 請問從起點start走到終點end的最高成功機率是多少? 如果完全沒有路徑可以抵達,則返回0。
題目敘述 664. Strange Printer 有一台奇怪的印表機, 每次操作只能連續印同樣的字母,但是列印的長度可以自由控制。 而且,印刷的時候,可以蓋過去舊的字元。 (這邊當然不合常理,讀者可以理解成塗了立可帶再蓋過去的情境) 給定一個輸入字串s,請問最少需要幾次操作,才能印出字串s?
給定一個整數陣列arr,和一串區間XOR請求queries。 請計算queries所請求的區間XOR值,並且以陣列的形式返回答案。
Path with Maximum Probability 題目給定一個無向圖(雙向移動皆可), 提供每條邊的起終點,和每條邊對應的通過時的成功機率。 請問從起點start走到終點end的最高成功機率是多少? 如果完全沒有路徑可以抵達,則返回0。
題目敘述 664. Strange Printer 有一台奇怪的印表機, 每次操作只能連續印同樣的字母,但是列印的長度可以自由控制。 而且,印刷的時候,可以蓋過去舊的字元。 (這邊當然不合常理,讀者可以理解成塗了立可帶再蓋過去的情境) 給定一個輸入字串s,請問最少需要幾次操作,才能印出字串s?