Brute Force (Top-down)
index가 증가하는 Top-down방식. 마지막 종료 case에 유의한다. 완전 탐색이므로 시간 복잡도는 재귀 트리의 사이즈인 O(2^N), 공간 복잡도는 재귀 트리의 깊이만큼인 O(N).
//Java
class Solution {
public int climbStairs(int n) {
return climb_stairs(0, n);
}
public int climb_stairs(int i, int n){
if(i > n){
return 0;
}
if(n == i){
return 1;
}
return climb_stairs(i+1, n) + climb_stairs(i+2, n);
}
}//JavaScript ES6
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
return climb_stairs(0, n);
};function climb_stairs(start, end){
if(start > end) return 0;
if(start == end) return 1;
return climb_stairs(start+1, end) + climb_stairs(start+2, end);
}
Brute Force with memoization
memoization한 배열을 넘겨주는 것을 잊지말도록 한다. memoization을 사용하여 한 번 계산한 것은 다시 계산하지 않으므로 시간 복잡도는 O(N²)에서 O(N)으로 감소, 공간 복잡도는 그대로 O(N).
//Java
class Solution {
public int climbStairs(int n) {
int[] memo = new int[n+1];
return climb_stairs(0, n, memo);
}
public int climb_stairs(int i, int n, int[] memo){
if(i > n){
return 0;
}
if(n == i){
return 1;
}
if(memo[i] > 0){
return memo[i];
}
memo[i] = climb_stairs(i+1, n, memo) + climb_stairs(i+2, n, memo);
return memo[i];
}
}//JavaScript ES6
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
return climb_stairs(0, n);
};function climb_stairs(start, end, memo = []){
if(start > end) return 0;
if(start == end) return 1;
if(memo[start]){
return memo[start];
}else{
memo[start] = climb_stairs(start+1, end, memo) + climb_stairs(start+2, end, memo);
return memo[start];
}
}
Dynamic Programming (Bottom-up)
index가 감소하므로 Bottom-up 방식이며, 시작 지점인 base case 작성에 유의 하도록 한다. 시간 복잡도는 n까지 한 번만 반복하므로 O(N), 공간 복잡도는 n size만큼의 배열이 사용되므로 O(N).
//Java
class Solution {
public int climbStairs(int n) {
if(n==1){
return 1;
}
int[] dp = new int[n+1];
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i<=n; i++){
dp[i] = dp[i-1]+dp[i-2];
}
return dp[n];
}
}//JavaScript ES6
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n, memo = []) {
if(n==1) return 1;
let dp = [null,1,2];
for(let i = 3; i<=n; i++){
dp[i] = dp[i-1]+dp[i-2];
}
return dp[n];
};
Fibonacci method
1과 2에서 시작한다는 것을 유의할 것. 변수 두 개를 이용해 공간 복잡도를 O(1)까지 줄일 수 있음. 시간 복잡도는 N번째 피보나치 숫자를 계산하기 위해 N번의 반복이 요구되므로 O(N).
//Java
class Solution {
public int climbStairs(int n) {
if(n == 1){
return 1;
}
int first = 1;
int second = 2;
for (int i = 3; i <= n; i++){
int third = first + second;
first = second;
second = third;
}
return second;
}
}//JavaScript ES6
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
if(n == 1){
return 1;
}
let first = 1;
let second = 2;
for(let i = 3; i<=n; i++){
const third = first+second;
first = second;
second = third;
}
return second;
};