1196踩方格（C++）

给个赞吧，给跪了

题目题目

/*

1196：踩方格

【题目描述】

有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设：

a、每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；

b、走过的格子立即塌陷无法再走第二次；

c、只能向北、东、西三个方向走；

请问：如果允许在方格矩阵上走n步，共有多少种不同的方案。2种走法只要有一步不一样，即被认为是不同的方案。

【输入】

允许在方格上行走的步数n(n≤20)。

【输出】

计算出的方案数量。

【输入样例】

2

【输出样例】

7

要做题首先我们先要知道这道题的题目是什么意思

 总结题目就是说在一个无限范围内的方格里面有一个初始点，要求这个点就是只可以走上,左,右，然后呢走过的格子不可以再走了，最后要求你根据已知的步数算出可能性。

思路：

这道题没有什么思路，就是一个举例子的题目

先看一下输入样例吧，输入2

然后根据题目要求的不可以走下，所以我们可以随机得到一个表格

其中小黑点（小黑子）代表了初始点，绿色代表着第一次到达的地方，蓝色代表第二次，红色第三次。

当输入的次数为1时，小黑子只可以走上左右，即3种情况

当输入为2时则为以下情况，7种可能，（注意，重复的证明走到哪里的有那么多可能）

输入为3就是

次数为3时注意小黑子左上和右上的蓝色因为小黑子上面的绿色没有走过，所以可以往那里走，所以还有2种可能不可以省略哦。

通过上面的测试可以看出次数为1,2,3时，可能数分别为3,7,13。

然后。。。。。。找规律。。。。。。

额。。。。。

很难找啊

最后还是发现了是3*2+7=13

所以规律就是i=（i-2）*2+（i-1）

然后就可以做了

真的很麻烦啊

*/

#include<iostream> 

#include<cstring>

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++) //for循环循环个数

        a[i]=2*a[i-1]+a[i-2];  //公式，当前的等于后面第一个*2加后面第二个

    cout<<a[n]<<endl; //输出答案

    return 0;

}

目前up也是没有找到更好的方法了，如果有，那么欢迎大家在下面评论区讨论回答，up会根据回答来更改文稿的，谢谢大家。最后请求大家点个赞吧！