LeetCode 솔루션

[Easy - wk3 - Q2] 70. Climbing Stairs

Chloe 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.05.16 17:01

10,853 조회
4 댓글
0 추천
0 비추천
목록

글검색

게시글 쓰기

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

#leetcode, #문제풀이, #easy, #amazon, #microsoft, #expedia, #uber, #google, #adobe, #yahoo, #oracle, #goldman sachs, #bloomberg, #apple, #intel, #math, #dynamic programming, #memoization

링크

https://leetcode.com/problems/climbing-stairs/ 5440 회 연결

익명
작성일 2022.05.18 16:38

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]

python

Time Limit Exceeded

[code=python]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)[/code]

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

[code=python]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]
        [/code]

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

[code=python]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][/code]

익명
작성일 2022.05.18 17:19

defaultdict in Python
https://www.geeksforgeeks.org/defaultdict-in-python/

익명
작성일 2022.05.24 11:20

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

익명
작성일 2022.05.25 01:17

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, {});
};