[LeetCode] 0070. climbing stairs

Explore diverse LeetCode solutions in Python, C++, JavaScript, SQL, and TypeScript. Ideal for interview prep, learning, and code practice in multiple programming languages. Github Repo Link

內容目錄

Easy

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?

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

Constraints:

1 <= n <= 45

Python

				
					class Solution:
    # time complexity: O(n)
    # space complexity: O(n)
    # Cashe with brute force
    # def climbStairs(self, n: int) -> int:
    #     memo = [0] * (n+1)
    #     return self.climb_Stairs(0, n, memo)

    # time complexity: O(n)
    # space complexity: O(n)
    # def climb_Stairs(self, i: int, n: int, memo: list) -> int:
    #     if (i > n):
    #         return 0
    #     if (i == n):
    #         return 1
    #     if (memo[i]):
    #         return memo[i]
    #     memo[i] = self.climb_Stairs(i+1, n, memo) + \
    #         self.climb_Stairs(i+2, n, memo)
    #     return memo[i]

    # time complexity: O(n)
    # space complexity: O(b)
    # Dynamic Programming
    # def climbStairs(self, n: int):
    #     if n == 1:
    #         return 1
    #     dp = [0] * (n + 1)
    #     dp[1] = 1
    #     dp[2] = 2
    #     for i in range(3, n+1):
    #         dp[i] = dp[i-1] + dp[i-2]
    #     return dp[n]

    # time complexity: O(n)
    # space complexity: O(1)
    # Fibonacci Number
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        first = 1
        second = 2
        third = 0
        for i in range(3, n+1):
            third = first + second
            first = second
            second = third
        return second


n = 50
print(Solution().climbStairs(50))

Easy

Python

相關文章