LeetCode 솔루션 분류
[Easy - wk3 - Q2] 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
태그
#leetcode, #문제풀이, #easy, #amazon, #microsoft, #expedia, #uber, #google, #adobe, #yahoo, #oracle, #goldman sachs, #bloomberg, #apple, #intel, #math, #dynamic programming, #memoization
관련자료
-
링크
댓글 4
Jack님의 댓글
- 익명
- 작성일
python
Time Limit Exceeded
*** 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.
*** 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.
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.
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.
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, {});
};
