#include <bits/stdc++.h>
using namespace std;
int a[30];
int main()
{
    int n,i;
    cin>>n;
    a[1]=3;
    a[2]=7;
    for(i=3;i<=n;i++)
        a[i]=2*a[i-1]+a[i-2];
    cout<<a[n]<<endl;
    return 0;
}

方法二：dfs:

#include <bits/stdc++.h>
using namespace std;
long long n, sum;
int dx[3] = {0, 0, 1};
int dy[3] = {-1, 1, 0};
bool vis[100][100];

int f(int x, int y, int step) {
    if (step >= n) {
        return 1;
    }
    vis[x][y] = true;
    int num = 0;
    for (int i = 0; i < 3; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (vis[nx][ny]) continue;
        num += f(nx, ny, step + 1);
    }
    vis[x][y] = false;
    return num;
}

int main() {
    cin >> n;
    sum = f(25, 25, 0); //在第一象限移动，防止vis越界
    cout << sum;
    return 0;
}

方法三：DFS，用sum全局累计次数，递归函数没有返回值

#include <bits/stdc++.h>
using namespace std;
long long n, sum;
int dx[3] = {0, 0, 1};
int dy[3] = {-1, 1, 0};
bool vis[100][100];

void f(int x, int y, int step) {
    if (step >= n) {
        sum++;
        return;
    }
    
    for (int i = 0; i < 3; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (vis[nx][ny]) continue;
        vis[x][y] = true;
        f(nx, ny, step + 1);
        vis[x][y] = false;
    }
}

int main() {
    cin >> n;
    f(25, 25, 0); //在第一象限移动，防止vis越界
    cout << sum;
    return 0;
}