[LeetCode] 70. Climbing Stairs

문제

DP 문제이다.

n개의 계단이 있을 때, 한 번에 1개 또는 2개의 계단을 올라갈 수 있다.

꼭대기에 오르기까지 계단을 오르는 방법이 몇 가지 인가?

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

Climbing Stairs - LeetCode

 

풀이

n번 째 계단에 도달하기 위해서는

1) n-1번 째 계단에서 1개의 계단을 오르기

2) n-2번 째 계단에서 2개의 계단을 오르기

위 2가지의 방법이 있다.

 

따라서, 이를 1개 계단을 도달하는 것 부터 n개 계단 까지 순서대로 계산하여 저장해 나가면 된다.

1개의 계단을 도달하는 방법은 1가지 이므로, 미리 저장하고 2개 계단부터 계산한다. (예외 처리)

 

코드

public int climbStairs(int n) {

    int[] ways = new int[n + 1];    // ways[i] : i번 째 계단을 오르는 방법의 수
    ways[0] = ways[1] = 1;

    for (int i = 2; i <= n; i++)
      ways[i] = ways[i - 1] + ways[i - 2];

    return ways[n];
}