CMU: Tiling

/// Tiling 1
#include <bits/stdc++.h>

using namespace std;

int main(){

    int n, m;
    cin >> n >> m;

    long long dp[n + 1];
    dp[0] = 1;
    for(int i=1;i<=n;i++){
        if(i - m < 0) dp[i] = dp[i - 1];
        else dp[i] = dp[i - 1] + dp[i - m];
    }

    cout << dp[n];

    return 0;
}

/// Tiling 2
#include <bits/stdc++.h>

using namespace std;
const int N = 30;
int three[N + 10], two[N + 10];

int main(){

    three[0] = 1;
    three[1] = 0;
    two[0] = 0;
    two[1] = 1;

    for(int i=2;i<=N;i++){
        three[i] = three[i - 2] + two[i - 1] + two[i - 1];
        ///        full area      top          bottom

        two[i] = three[i - 1] + two[i - 2];
    }

    int q;
    scanf("%d", &q);

    while(q--){
        int n;
        scanf("%d", &n);
        printf("%d\n", three[n]);
    }

    return 0;
}

/// Tiling 3
#include <bits/stdc++.h>

using namespace std;
using lli = long long;
const lli mod = 1e9 + 7;
const int N = 1e3 + 10;
lli full[N], top[N], bottom[N];

int main(){

    int n;
    scanf("%d", &n);

    full[1] = 1;
    full[2] = 2;
    top[2] = 1;
    bottom[2] = 1;

    for(int i=3;i<=n;i++){
        full[i] = (full[i - 1] + full[i - 2] + top[i - 1] + bottom[i - 1]) % mod;
        top[i] = (full[i - 2] + bottom[i - 1]) % mod;
        bottom[i] = (full[i - 2] + top[i - 1]) % mod;
    }

    printf("%lld", full[n]);

    return 0;
}