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

这一题光看字面意思还是很难推出递推式的，我们来看一张图： 以上是一张当n == 2时的路线图。从中可以看出从出发点延伸出了三条路径‘1’，‘2’，‘3’。垂直的路径‘2’延伸出了三条新的路径——‘6’、‘7’、‘8’。其中有一条垂直的，两条水平的。而从出发点延伸出的另外两条线路——‘1’、‘3’却只各自延伸出了一条垂直的、一条水平的。 所以从中我们不难看出，垂直的路径会延伸出三条新的；水平的路径会延伸出两条新的，这样就可以开始算递推式了。 我们可以用一个数组a来存放当n == ai时的移动方案总数；用b来存放当前水平的路径数量（并处于叶部分），我们就可以很容易推出： b[i] = b[i - 1] + (a[i - 1] - b[i - 1]) * 2; 然后： a[i] = a[i - 1] + b[i]; 代码如下：

前置：f(n)为第n步的可能数量。 每一个点可以选向上向右和向左三种选择。再下一次选择时上一次选择的向上可以有三种选择，其余的可以有两种选择。所以，选择上的会多一种选择机会。我们提取公因式，每一个点都有两种选择即2*f(n-1),特殊选择向上的时会多一次，而再上一次时每一个点都有一次选择向上的可能性，所以是f(n-2). 得出：f(n) = f(n-1)*2+f(n-2)

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

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

#include <bits/stdc++.h> using namespace std; int n; int north[25],east[25],west[25]; void work() { cin>>n; north[1]=east[1]=west[1]=1; for(int i=2;i<=n;i++) { north[i]=east[i-1]+west[i-1]+north[i-1]; east[i]=north[i-1]+east[i-1]; west[i]=north[i-1]+west[i-1]; } cout<<north[n]+east[n]+west[n]; } int main() { work(); return 0; }