今天是紀錄LeetCode解題的第七十天

第七十題題目：You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

你正在爬樓梯，要到達頂端n需要走幾步。

每次你可以選擇爬1階樓梯或2階，可以用多少種不同的方式爬到頂峰？

解題思路

這題是很經典的dp題目，其原理和費波納契數列一樣，轉移方程式都是dp[i] = dp[i-1] + dp[i-2]，因為一次可以爬一階或兩階，所以能爬到第i階的方法數等於能到達前兩階(i-1、i-2)的方法數相加

程式碼

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        dp = [0] * (n + 1)
        dp[1],dp[2] = 1,2
        for i in range(3,n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

這題太簡單了不做太多贅述