70. Climbing Stairs

주어진 계단을 오를 때, 각 단계마다 1단계 또는 2단계씩 올라가는 방법의 수를 계산하는 문제입니다.

문제 설명:

당신은 n개의 계단을 올라야 합니다. 한 번에 1단계 또는 2단계씩 올라갈 수 있을 때, n개의 계단을 올라갈 수 있는 방법의 수를 계산하세요.

예를 들어, n = 3인 경우, 다음과 같은 방법으로 3개의 계단을 올라갈 수 있습니다:

1단계 -> 1단계 -> 1단계
1단계 -> 2단계
2단계 -> 1단계
따라서 3개의 계단을 올라가는 방법은 총 3가지입니다.

예시:

입력: n = 2

출력: 2

설명: 2개의 계단을 올라가는 방법은 2가지입니다: 1단계 -> 1단계 또는 2단계 한 번.

입력: n = 3

출력: 3

설명: 3개의 계단을 올라가는 방법은 3가지입니다 (위의 예시 참고).

이 문제를 해결하는 가장 일반적인 방법은 다이나믹 프로그래밍(Dynamic Programming)을 사용하는 것입니다. 현재 계단 수를 올라갈 때의 방법의 수를 저장하면서 이전 단계의 방법의 수를 활용하여 계산하는 방법입니다. 

public int ClimbStairs(int n) {
    if (n == 1) {
        return 1; // 1개의 계단일 경우 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];
}

다이나믹 프로그래밍을 사용하여 ClimbStairs 함수를 구현합니다. 배열 dp를 사용하여 계단 수에 따른 방법의 수를 저장하며, 초기 값으로 1개와 2개의 계단을 올라가는 방법의 수를 설정합니다. 그런 다음, 3개 이상의 계단을 올라가는 방법의 수는 이전 단계의 방법의 수를 활용하여 계산합니다. 최종적으로 dp[n]에 저장된 값이 n개의 계단을 올라가는 방법의 수를 나타냅니다.