70. Climbing Stairs (계단 오르기)

당신은 계단을 오르고 있습니다. 정상에 오르기 위해서는 n개의 단계가 필요합니다.
매번 당신은 1단계 또는 2단계를 오를 수 있습니다. 당신은 몇 가지 다른 방법으로 정상에 오를 수 있습니까?

예시 1:

입력: n = 2
출력: 2
설명: 정상에 오르는 두 가지 방법이 있습니다.
1. 1단계 + 1단계
2. 2단계

 

예시 2:

입력: n = 3
출력: 3
설명: 정상에 오르는 세 가지 방법이 있습니다.
1. 1단계 + 1단계 + 1단계
2. 1단계 + 2단계
3. 2단계 + 1단계

 

조건:

• 1 <= n <= 45

 

정답:

public class Solution {
    public int ClimbStairs(int n) {
        if (n == 1) 
            return 1;

        int[] result = new int[n + 1];
        result[1] = 1;
        result[2] = 2;

        for (int i = 3; i <= n; i++) 
        {
            result[i] = result[i - 1] + result[i - 2];
        }

        return result[n];
    }
}

해설: 

1일때는 하나뿐이니 1을 return 해주고 그 외의 경우엔

n-1 + n-2 에서의 경우의 수를 합치면 n번째의 가능한 경우의 수가 나오므로 앞에서부터 분할하여 풀었습니다.