C++:: 프로그래머스 < 3 x n 타일링 >

점화식을 만드는게 포인트인 문제이다. 하지만 점화식을 만드는것이 쉽지않은 어려운 문제이다.
점화식은 다음과 같다.
f(n) = 3f(n-2) + 2f(n-4) + 2f(n-6) + .... + 2;

#include <string>
#include <vector>
using namespace std;

int solution(int n) {
    if (n % 2) return 0;
    vector<long long> dp(n+1, 0);
    dp[2] = 3;
    long long sum = 0;
    for (int i=4; i<=n; i+=2) {
        dp[i] = (dp[i-2] * 3 + sum * 2 + 2) % 1000000007;
        sum += dp[i-2];
    }
    return dp[n];
}