Leetcode 70 題
有人問我：烤冷面你這兩周怎么總搞簡單題？我想說：一步一步來～
題干簡述
給定：
- 假設你正在爬樓梯，需要爬 n 階你才能到達樓頂，
- 每次你可以爬 1 或 2 個臺階，
要求：計算出有多少種爬樓梯的方式，
解題思路
如果我們縮小視野（把大問題化為小問題），爬到第 n 階臺階有兩種方式：
- 從 n-1 階爬一級臺階
- 從 n-2 階爬兩級臺階
用公式表達：dp[n] = dp[n?1] + dp[n?2]，其中的特例是：dp[0]=1 和 dp[1]=1，
嚯！這不就是LeetCode 509(斐波那契數列)么，
代碼實作
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 2:
return n
dp = [0]*(n+1)
dp[0] = 1
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
復雜度
時間復雜度O(n)，空間復雜度O(n)，
關注公眾號：「腐蝕腳本」，加入交流群，
文章歸檔：烤冷面講演算法系列
轉載宣告：本文章允許轉載，原文地址：「動態規劃」LeetCode 70(爬樓梯)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/549064.html
標籤：其他
下一篇：2023 雜想