[DP - 1D, Medium] Domino and Tromino Tiling

https://leetcode.com/problems/domino-and-tromino-tiling/description/?envType=study-plan-v2&envId=leetcode-75

이건 못풀겠어서 답을 봤다.
https://leetcode.com/problems/domino-and-tromino-tiling/solutions/116581/detail-and-explanation-of-o-n-solution-why-dp-n-2-d-n-1-dp-n-3/?envType=study-plan-v2&envId=leetcode-75

Zhengkai Wei이라는 분이 설명을 잘 해주셨음

핵심

• dp[n-1]과 dp[n-2]에서 올 수 있는 길은 한 가지씩 밖에 없다.
  • dp[n-1] 에서 -> 세로막대기 하나 추가
  • dp[n-2] 에서 -> 가로막대기 두개 추가
• dp[n-3] ~ dp[0]에서 올 수 있는 길은 두 가지씩 있다. (트리미노까지 사용)
• 따라서, dp[n] = dp[n-1] + dp[n-2] + (2 * (dp[n-3] ~ dp[0])) 이다.
• 이것은 아래 공식에 따라 dp[n] = 2 * dp[n-1] + dp[n-3] 으로 나타낼 수 있다.

dp[n]= dp[n-1] + dp[n-2] + 2*(dp[n-3]+...+d[0])
= dp[n-1] + dp[n-2] + dp[n-3] + dp[n-3] + 2*(dp[n-4]+...+d[0])
= dp[n-1] + dp[n-3] + (dp[n-2] + dp[n-3] + 2*(dp[n-4]+...+d[0]))
= dp[n-1] + dp[n-3] + dp[n-1]
= 2 * dp[n-1] + dp[n-3]

class Solution {
    public int numTilings(int n) {
        int MOD = 1_000_000_007;
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 5;

        long[] dp = new long[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 5;

        for (int i=4; i<=n; i++) {
            dp[i] = (2 * dp[i - 1] % MOD + dp[i - 3] % MOD) % MOD;
        }

        return (int) dp[n];
    }
}