一、题目

资源限制 时间限制：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;
} 

四、题目链接

ALGO-981 过河马