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로 구현

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];
    }
}