https://leetcode.com/problems/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
첫 번째 풀이
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
return getSteps(n);
};
var getSteps = function(n) {
if (n === 0) {
return 1;
} else if (n < 0) {
return 0;
} else {
return getSteps(n-1) + getSteps(n-2);
}
}

Recursion 을 써서 간단하게 해결해보려했는데 테스트 케이스 크기가 커지면서 시간 초과에 걸려서 실패했다. 메모이제이션을 적용해줘야겠다.
두 번째 풀이 - 성공
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
return getSteps(n);
};
var getSteps = function(n) {
if (memoize[n]) {
return memoize[n];
} else if (n === 0) {
return 1;
} else if (n < 0) {
return 0;
} else {
if (memoize[n-1] && memoize[n-2]) {
memoize[n] = memoize[n-1] + memoize[n-2];
return memoize[n-1] + memoize[n-2];
} else {
return getSteps(n-1) + getSteps(n-2);
}
}
}
var memoize = {
2: 2,
3: 3
};

메모이제이션을 적용해서 해결해줬는데, 문제의 예시로 나와줬던 n=2, n=3 일 때의 값을 memoize 객체에 넣어주고 시작해야 통과한다. 객체에 아무 것도 없이 시작하면 할당부터 안되서 똑같이 실패한다. n=2, n=3 을 적용해줬으므로 n=4 인 값을 확인할 때를 시작으로 해당되는 값을 memoize 객체에 넣어주게 된다. 그렇게 계속 상위의 값들까지 memoize 객체에 할당되면 재귀 함수의 깊이가 깊어질 필요 없이 점점 빨리 return 되므로 속도가 개선되어 통과할 수 있다.
'알고리즘 > LeetCode' 카테고리의 다른 글
[Leetcode][Javascript][Medium] 7. Reverse Integer (0) | 2021.07.04 |
---|---|
[Leetcode][Javascript][Medium] 2. Add Two Numbers (0) | 2021.07.02 |
[Leetcode][Javascript][Easy] 1. Two Sum (0) | 2021.07.01 |
[Leetcode][Javascript][Easy] 155. Min Stack (0) | 2021.06.30 |
[Leetcode][Javascript][Easy] 20. Valid Parentheses (0) | 2021.06.28 |
댓글