iT邦幫忙

2022 iThome 鐵人賽

DAY 15
0
自我挑戰組

LeetCode Top 100 Liked系列 第 15

[Day 15] Climbing Stairs (Easy)

  • 分享至 

  • xImage
  •  

70. Climbing Stairs

Question

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 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

Solution 1: Recursive (TLE)

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 0 or n == 1:
            return 1
        return self.climbStairs(n - 2) + self.climbStairs(n - 1)

Time Complexity: O(2^N)
Space Complexity: O(1)

Solution 2: DP

class Solution:
    def climbStairs(self, n: int) -> int:
        # If n == 0 or 1
        ansList = {
            0 : 1, 
            1 : 1
        }
        for i in range(2, n + 1):
            ansList[i] = ansList[i - 1] + ansList[i - 2]
        return ansList[n]

Time Complexity: O(N)
Space Complexity: O(N)

Solution 3: Enhanced DP

class Solution:
    def climbStairs(self, n: int) -> int:
        one, two = 1, 1
        for i in range(2, n + 1):
            temp = two
            two += one
            one = temp
        return two

Time Complexity: O(N)
Space Complexity: O(1)

Reference

https://leetcode.com/problems/climbing-stairs/discuss/2580551/100-Best-Solution-Explained

Follow-up: Min Cost Climbing Stairs、Fibonacci Number

TODO

Time Complexity: O()
Space Complexity: O()

Follow-up (N年前在實驗課遇到的變形): All Possible Combinations Of Steps On A Staircase With N Steps

Reference

https://www.adimation.info/2020/04/24/all-possible-combinations-of-steps-on-a-staircase-with-n-steps/


上一篇
[Day 14] Merge Two Sorted Lists (Easy)
下一篇
[Day 16] Longest Increasing Subsequence (Medium)
系列文
LeetCode Top 100 Liked77
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言