---
title: "#70 Climbing Stairs"
tags: LeetCode, Top100
---
#70 Climbing Stairs
==

題目描述
--
You are climbing a stair case. It takes n steps to reach to the top.

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

Example 1:
--
>Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

解題思維
--
就是一個費式數列，可以用暴力解、遞迴解、DP解、公式解。
這邊用DP解。

Dynamic Programming
--

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

題外話
--
下面順便練習一下遞迴解與尾遞迴

#### 遞迴
>不過數字太大，記憶體就直接炸開了

class Solution:
    def climbStairs(self, n: int) -> int:
        def Recursive(n):
            if n <= 2:
                return n
            else:
                return Recursive(n-1)+Recursive(n-2)
        return Recursive(n)

#### 尾遞迴
>不過尾遞迴需要有編譯器支援才能轉成迭代，不然還是會占用記憶體位置。

class Solution:
    def climbStairsTailRecursive(self, n: int) -> int:
        def TailRecursive(n, right=1, left=0):
            if n == 1:
                return left+right
            else:
                return TailRecursive(n-1, left+right, right)
        return TailRecursive(n)