[LeetCode] 26.Climbing Stairs

https://leetcode.com/problems/climbing-stairs/

Climbing Stairs - LeetCode

 

1. Problem

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

 

2. Code

package leetCode;

public class climbingStairs {

	public static void main(String[] args) {
		System.out.println("답: " + climbStairs(5));
	} 
	
	public static int climbStairs(int n) {
		int[] temp = new int[n+1];
		if(n <= 2) {
			return n;
		} else {
			temp[1] = 1;
			temp[2] = 2;
			return nextStep(n-1, temp) + nextStep(n-2, temp);
		}
    }
	
	public static int nextStep(int n, int[] temp) {
		if(temp[n] > 0) {
			return temp[n];
		} else {
			temp[n] = nextStep(n-1, temp) + nextStep(n-2, temp);
		}
		return temp[n];
	}
}

 

3. Report

이 문제는 1계단 올라가느냐 2계단 올라가느냐기때문에 n-1호출과 n-2 호출의 합인 재귀로 풀 수 있다. 

처음엔 단순 재귀형식으로 풀었더니 작은 수에서는 풀리지만 큰 수에서는 시간초과가 나왔다.

구글링을 해보니 이렇게 풀면 방문했던 n번째도 계속 방문하게 되어서 2ⁿ 시간이 걸린다더라,,

방법은 int[] temp를 만들어서 한 번 방문했던 곳은 다시 계산 안해도 될 수 있게 코드를 짰다.

재귀로 코드를 짜다보면 내가 맞게 찾는지 헷갈릴때가 있어서 직접 손으로 그려보는 것이 좋다