[LeetCode] Climbing Stairs

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

Climbing Stairs - LeetCode

1스텝 혹은 2스텝씩 이동하여 계단을 오르는 문제이다. 전형적인 DP 문제이다. 해당 칸까지 가는 수는 이전 칸에서 해당 칸에 오는 수만큼이기 때문이다.

Kn = Kn-1 + Kn-2의 간단한 점화식을 찾아서 구현하였다.

class Solution {
public:
    int climbStairs(int n) {
        vector<int> DP(n);
        DP[0]=1;
        if(n==1)
            return DP[0];
        DP[1]=2;
        for(int i=2;i<n;i++) {
            DP[i]=DP[i-1]+DP[i-2];
        }
        
        return DP[n-1];
    }
};