ybt1196 踩方格
【题目描述】
有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设：
a、每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；
b、走过的格子立即塌陷无法再走第二次；
c、只能向北、东、西三个方向走；
请问：如果允许在方格矩阵上走n步，共有多少种不同的方案。2种走法只要有一步不一样，即被认为是不同的方案。
【输入】
允许在方格上行走的步数n(n≤20)。
【输出】
计算出的方案数量。
【输入样例】
2
【输出样例】
7
分析题目，可知本题的行走规则和过河卒相似，但路径不能重走
先看方向，设上北下南左西右东，则只能往前左右走
很容易知道，n=1时，答案为3。
那么当n=2的时候，就可以把问题分成三部分:
第一步朝上走，可以近似的看成在新起点上随便走一步，有3种情况，
第一步朝左走，可以近似的看成在新起点上禁止往右走，有2种情况，
同理，第一步往右走，也是两种情况，那么n=2时，就是7种情况。
设n=i时，答案为f~i~,那么显然n=i时，第1步往上走会有f~i-1~种情况，那么只要正确求出第一步往左右的情况，答案就可求了。
这里统称往左和往右为往侧面走。
只走一步，有1一种情况；
走2步，有两种情况；
走3步，有5种情况（f~1~+2）
·········
所以往侧面的路径可以理解为网络的总线结构，一条射线上每隔一个单位生出一个分支，越早生出的分支生长越大，这样就可以写出n=i时往侧面走的表达式：
f~i-1~+f~i-2~+···+f~1~+2
因为侧面包括左右，所以：
f~i~=2(f~i-1~+f~i-2~+···+f~1~+2)+f~i-1~
递推式写好了，边界条件也很明确：f~1~=3
接下来就可以打代码了
#include<iostream>
using namespace std;
int f[25],n;
int main() {
f[0]=0;
f[1]=3;
cin>>n;
if(n==0) {//特判
cout<<0;
return 0;
}
for(int i=2;i<=n;i++) {
for(int j=i-2;j>=1;j--) {
f[i]+=2*f[j];//2*(f[i-1]+...+f[111])
}
f[i]+=f[i-1]+4;//2*2+f[i-1]
}
cout<<f[n]<<endl;
return 0;
}