[Leetcode,c++] Climbing Stairs

문제

Climbing Stairs - LeetCode

 

코드

class Solution {
public:
    int climbStairs(int n) {
        int dp[46];

        dp[1]=1;
        dp[2]=2;

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

 

풀이

간단한 dp 문제였습니다. 먼저 첫 번째 계단을 올라가는 경우는 (1칸씩 올라가기) 한 가지이고 두 번째 계단을 올라가는 경우는(1칸+1칸, 2칸)으로 두 가지입니다. 따라서 초기값으로 설정을 해주고 세 번째 칸부터의 계단은 이전에 한 칸으로 올라왔을 경우와 두 칸으로 올라온 경우를 더해주면 됩니다.