[프로그래머스] 2xn 타일링

- 해보다보니 피보나치 인 걸 알게됨

- 피보나치 dp 는 그냥 메모이제이션만 잘 해주면 갈무리 됨

 

class Solution {
    // 1 1 2 3 5
    // n=1 -> 1
    // n=2 -> 2
    // dp
    // int[]
    public int solution(int n) {
        final int CONSTANT = 1000000007;
        int[] dp = new int[n+2];
        dp[0] = 1;
        dp[1] = 1;
        for(int i=2; i<n+2; i++) {
            dp[i] = (dp[i-2] + dp[i-1]) % CONSTANT;
        }
        return dp[n];
    }
}