备战蓝桥杯——算法训练之过河马
一、题目
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
在那个过河卒逃过了马的控制以超级超级多的走法走到了终点之后，这匹马表示它不开心了……
于是，终于有一天，它也过河了！
由于过河马积累了许多的怨念，所以这次它过了河之后，再也没有什么东西可以限制它，它可以自由自在的在棋盘上驰骋。一开始，它是在一个n行m列棋盘的左下角（1,1）的位置，它想要走到终点右上角（n，m）的位置。而众所周知，马是要走日子格的。可是这匹马在积累了这么多怨念之后，它再也不想走回头路——也就是说，它只会朝向上的方向跳，不会朝向下的方向跳。
那么，这匹马它也想知道，它想从起点跳到终点，一共有多少种走法呢？
输入格式
第一行两个数n，m，表示一个n行m列的棋盘，马最初是在左下角（1,1）的位置，终点在右上角（n，m）的位置。
输出格式
输出有一行，一个数表示走法数。由于答案可能很大，所以输出答案除以1000000007所得的余数即可。
样例输入
4 4
样例输出
2
数据规模和约定
n<=100,m<=100
二、思路
如图，我们理一下思路，从左下角跳到右上角，用一个二维数组来存储跳到每个点的总步数。我们来逆推，（其中2,3和3,2只可能是从1,1跳来的。），以黄点为例，他可能是A、B、C、D任意一点跳来的。然后，要判断一下A、B、C、D在不在棋盘内。
然后题目说答案可能很大，输出答案除以1000000007所得的余数即可。那为了防止爆掉，我们每加完一条路的总步数之后就取一遍余。
题目解法思路如上述，但是这里有一个我之前从来没有注意过的问题，导致我一直只有90分。那就是我一直习惯于在main函数内声明变量。。。
具体原因是在这篇博客里看的，详情点击传送门。
其实就是说在main函数外面开一个数组，他的内存分配在数据区里；如果在main函数内部开数组，内存分配在栈区内。一般来说栈区的内存是比较小的，所以平常开一些小一点的数组是没问题的；但如果题目要求的数组比较大，那就会出现爆出的问题。
三、题解
#include<iostream>
using namespace std;
int n,m;
int cb[105][105];
int main(){
cin>>n>>m;
cb[2][3] = cb[3][2] = 1;
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
if(i-1 >=1 && j-2 >= 1)
{
cb[i][j] += cb[i-1][j-2];
cb[i][j] %= 1000000007;
}
if(i-2 >=1 && j-1 >= 1)
{
cb[i][j] += cb[i-2][j-1];
cb[i][j] %= 1000000007;
}
if(i-2 >=1 && j+1 <= m)
{
cb[i][j] += cb[i-2][j+1];
cb[i][j] %= 1000000007;
}
if(i-1 >=1 && j+2 <= m)
{
cb[i][j] += cb[i-1][j+2];
cb[i][j] %= 1000000007;
}
}
}
cout<<cb[n][m];
return 0;
}