#include <bits/stdc++.h>

using namespace std;

// C++ 算法篇 递推
// https://blog.csdn.net/weixin_43736974/article/details/108246801
/*
【问题分析】
用 f(n) 表示 n×3 的路面有多少种不同的铺设方案。把路面看成n行3列，则问题可以分成两种情况考虑，一种是最后一行用 3 块 1×1 的瓷砖铺设；
另一种是最后两行用 1 块 2×2 和 2 块 1×1 的瓷砖铺设(最后两行就有两种铺法)，第一种铺法就转换为 f(i-1) 的问题了，第二种铺法就转换成 f(i-2) 的问题了。
根据加法原理，得到的递推关系式为 f(i) = f(i-1) +f(i-2)×2，边界为 f(0)=1，f(1)=1。
 */

int f(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (n == 2) return 3;
    return dp(n - 1) + 2 * dp(n - 2);
}

int main() {
    int n;
    n = 3;

    cout << dp(n) << endl;

    return 0;
}