LeetCode 솔루션 분류

[Easy - wk3 - Q2] 70. Climbing Stairs

컨텐츠 정보

본문

70. Climbing Stairs 


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

관련자료

댓글 4

Jack님의 댓글

  • 익명
  • 작성일
python

Time Limit Exceeded

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


*** Memoization ***
Runtime: 32 ms, faster than 83.88% of Python3 online submissions for Climbing Stairs.
Memory Usage: 13.8 MB, less than 58.27% of Python3 online submissions for Climbing Stairs.

class Solution:
    dp = collections.defaultdict(int)
    
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        
        if self.dp[n]:
            return self.dp[n]
        
        self.dp[n] = self.climbStairs(n-1) + self.climbStairs(n-2)
        return self.dp[n]
        


*** Tabulation ***
Runtime: 60 ms, faster than 9.43% of Python3 online submissions for Climbing Stairs.
Memory Usage: 13.9 MB, less than 58.27% of Python3 online submissions for Climbing Stairs.

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

mingki님의 댓글

  • 익명
  • 작성일
C++
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Climbing Stairs.
Memory Usage: 5.8 MB, less than 83.45% of C++ online submissions for Climbing Stairs.
class Solution {
public:
    int climbStairs(int n) {
        int curr = 1, prev = 0;
        for (int i = 1; i <= n; ++i) {
            curr += prev, prev = curr - prev;
        }
        return curr;
    }
};

dawn27님의 댓글

  • 익명
  • 작성일
Runtime: 77 ms, faster than 47.02% of JavaScript online submissions for Climbing Stairs.
Memory Usage: 42 MB, less than 34.99% of JavaScript online submissions for Climbing Stairs.
var climbStairs = function(n) {
    let counterFunc = (stairsRemaining, savedResult) => {    

        if (stairsRemaining < 0) return 0;
        if (stairsRemaining === 0) return 1;

        if (savedResult[stairsRemaining]) return savedResult[stairsRemaining];

        savedResult[stairsRemaining] = counterFunc(stairsRemaining-1, savedResult) + counterFunc(stairsRemaining-2, savedResult);

        return savedResult[stairsRemaining];
    }

    return counterFunc(n, {});
};
LeetCode 솔루션 357 / 1 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


알림 0