題目?
假設你正在爬樓梯。需要?n?階你才能到達樓頂。
每次你可以爬?1?或?2?個臺階。你有多少種不同的方法可以爬到樓頂呢？
示例 1：
輸入：n = 2 輸出：2 解釋：有兩種方法可以爬到樓頂。 1. 1 階 + 1 階 2. 2 階
示例 2：
輸入：n = 3 輸出：3 解釋：有三種方法可以爬到樓頂。 1. 1 階 + 1 階 + 1 階 2. 1 階 + 2 階 3. 2 階 + 1 階
思路?
寫法1?
class Solution:def climbStairs(self, n: int) -> int:if n==1:return 1# 1.確定dp數組及下標含義：dp[i]表示爬到i階有dp[i]種方法# 2.狀態轉移方程# dp[i] = dp[i-1]+dp[i-2]:第i階樓梯由第i-1階和第i-2階轉移過來# 3.初始化：dp[1]=1,dp[2]=2# 4.執行順序：順序依次執行即可dp = [0]*(n+1)dp[1] = 1dp[2] = 2for i in range(3,n+1):dp[i] = dp[i-1]+dp[i-2]return dp[n]寫法2
class Solution:def climbStairs(self, n: int) -> int:if n<3:return ndp1 = 1dp2 = 2res = 0for _ in range(n-2):res = dp1+dp2dp1,dp2 = dp2,resreturn res
)
