Climbing Stairs

너무 유명한 DP문제. 계단을 한 번에 1칸 ro 2칸 오를 수 있는데, 1번째 계단이면 1가지 방법, 2번째 계단이면 2가지 방법으로 오를 수 있다. 

3번째 계단은 3가지 방법으로. -> 1번째 계단에서 2칸, 2번째 계단에서 1칸

3번째 계단의 예를 잘 생각해보면 2칸 낮은 곳 + 1칸 낮은 곳의 경우의 수를 더하면 된다.

4번째 계단에 올라갈 수 있는 경우의 수를 생각해 보면, 4번째 계단으로 가는 방법을 생각해 보자. 2번째 계단에서 2칸 점프를 하거나 3번째 계단에서 1칸 점프를 하는 수 밖에 없다.

-> 그럼, 2번째 계단으로 갈 수 있는 경우의 수는? 땅에서 2칸 점프하거나, 1번째 계단에서 1칸 점프

-> 3번째 계단으로 가는 경우? 1번째 계단에서 2칸 점프, 2번째 계단에서 1칸 점프 -> 2번째 계단: 상단과 같다.

이를 정리해보면 4번째 계단으로 가는 방법은 2번째 계단에서 2칸 점프를 하면 되니, 2번째 계단으로 가는 모든 경우의 수 만큼 존재하고,

3번째 계단에서 1칸 점프를 하면 되니, 3번째 계단으로 가는 모든 경우의 수 만큼 존재한다.

그래서 -2번째 계단 + -1번째 계단 경우의 수 만큼 해당 계단의 경우의 수가 존재하는 것이다.

구현 방법은 배열을 하나 만들어서 Memoization을 활용해서 구현한다. 사실 완전탐색? 비스므리 한건데, 메모리를 희생해서 속도를 높인 알고리즘이라는걸 어디서 줏어들은거 같다. 종만북이었나?

class Solution {
public:
    int climbStairs(int n) {

        if(n==1) return 1;
        else if(n==2) return 2;

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