(Easy - DP) Leetcode - 70. Climbing Stairs

계단을 올라갈 때 n번째까지 갈 수 있는 방법의 수를 물어보는 문제입니다.

계단을 오를때 제한이 있는데 한 번에 1칸 또는 2칸씩 오를 수 있습니다.

 

이 뜻은 n번째 계단에 가기 위해서는 n-1번째 계단에서 1칸을 올라가거나 n-2번째 계단에서 2칸을 오를 수 있습니다.

이를 쉽게 Recursion으로 풀 수 있습니다.

 

    int climb(int n) {
        if (n == 0 || n == 1) // 안오르거나, 가장 첫 1칸
            return 1; // 방법의 수는 1
            
        // n번째 계단을 오르려면 n-1에서 한칸 또는 n-2에서 두 칸씩 오르면 된다
        return climb(n - 1) + climb(n - 2); 
    }

(이 방법은 잘 살펴보면 피보나치를 구할 때 사용하는 재귀방식과 비슷합니다.)

 

이를 더 최적화할 수 있는데 이 때 Dynamic Programming을 사용합니다.

n번째 계단으로 가기위해 n-1번째 계단이나 n-2번째 계단에서 올라갈 수 있습니다.

이때 n-1번째와 n-2번째 계단으로 갈 수 있는 방법의 수를 이전에 구해 저장해두면 다시 맨 처음 계단으로 돌아가지 않고 계산을 할 수 있습니다.

 

Memoization 방법

    int climbUp(int n, vector<int>& dp) {
        if (n == 0 || n == 1)
            return 1;

        if (dp[n]) // 이전에 n번째 계단까지 오르는 방법의 수를 구해놨다면
            return dp[n];
        
        dp[n] = climbUp(n - 1, dp) + climbUp(n - 2, dp);
        return dp[n]
    }

    int climbStairs(int n) {
        if (n < 2)
            return 1;
        vector<int> dp(n + 1, 0);
        return dp[n];
    }

 

Tabulation 방법

    int climbStairs(int n)
    {
        if (n == 0 || n == 1)
            return 1;

        std::vector<int> climb(n + 1, 1);

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

        return climb[n];
    }