思路

根据水平段方向约束推导递推，覆盖二十步边界。

参考程序（C++11）

#include <bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;long long a=1,b=3;if(n==0){cout<<1;return 0;}for(int i=2;i<=n;i++){long long t=2*b+a;a=b;b=t;}cout<<b<<'\n';}