[LeetCode/easy] Climbing-Stairs (C++)

leetcode.com/problems/climbing-stairs/

Climbing Stairs - LeetCode

전형적인 dp 유형의 문제였습니다. dp[n]을 정의해보면, n층을 오를 수 있는 모든 경우의 수를 의미합니다. 그리고 계단은 1 혹은 2만큼 오를 수 있습니다. 마지막 n번째에서 생각해보면, n-1층에서 1만큼 오르는 경우, n-2층에서 2만큼 오르는 경우 두가지를 생각할 수 있는데, 즉 n-1층을 오를 수 있는 모든 경우의 수와 n-2층을 오를 수 있는 모든 경우의 수를 더하면 n층을 오를 수 있는 모든 경우의 수를 구할 수 있음을 의미합니다. 따라서 점화식은 다음과 같습니다.

 

dp[n] = dp[n - 1] + dp[n - 2]

 

class Solution {
public:
    int dp[46];
    
    int climbStairs(int n) {
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        return dp[n];
    }
};