This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.
#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;
