# Climbing Stairs

**틀린 이유**\
1\. base case(boundary case) 를 잘못 세웠다. - dp\[1] = 1, dp\[2] = 2 (X)\
                                                                                 dp\[0] = 1, dp\[1] = 1(O)\
2\. 점화식을 잘못 세웠다. - dp\[n] = dp\[n-1] \* 2 - 1 (X)\
                                         dp\[n] = dp\[n-1] + dp\[n-2] (O)

**자료 구조(Data Structure)**\
Memoization을 위한 1차원 배열

**알고리즘**\
1\. base가 되는 sub-problem의 해를 구한다. - dp\[0], dp\[1]\
2\. 1의 sub-problem의 해를 통해 최종 해를 구한다. \
    문제에서 주어진 것처럼, 한번에 1 또는 2 step씩 올라갈 수 있다.\
    n개의 계단인 경우, 1개의 계단을 올라가는 경우 **또는** 2개의 계단을 올라가는 경우\
\=  **stairs(n) = stairs(n-1) + stairs(n-2)**

**알고리즘을 Java로 구현**

```java
class Solution {
    public int climbStairs(int n) {
        int dp[] = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        
        for(int i=2;i<=n;i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}
```