狗の题解

这道题用的是二维答案数组，最后只要对着坐标直接输出就行，但是，在数据处理和求状态转移方程上，这道题给本狗倒是挖了点坑...比如为啥小码君没把小蚂蚁直接踩死或者踩到左脚等等

开始正经讲题！

1，数据处理方面

这道题题面上说这只蚂蚁只能向右边和上面走，而且要从右下角走到左上角，要知道，C++的数组结构是从左上角往右下角扩大的，那如果真按照题面来写的话，将会极其繁琐...(可能你代码没敲完，键盘先起义了）所以我们要先把题面倒一下，让这只蚂蚁从左上角往右下角走，只能向左或向下移动，被踩掉的是左脚

2.状态转移方程

这道题的状态转移方程其实和蜜蜂路线那道题差不多，这只小 蚂蚁如果想要到右下角（此时我们已经把题面倒了一下），那就必须得到右下角上方的格子或左边的格子，根据加法原理并以此类推，除了可以一次到达的格子外，所有格子的路径总数都为上方和左方的格子路径数之和，即a[i][j]=a[i-1][j]+a[i][j-1];

3.敲键盘

现将一步到达的格子初始化，输入之后按照状态转移方程递推即可

记得开long long

#include<bits/stdc++.h>
using namespace std;
long long dp[25][25];
int a,b;
int main()
{
	dp[1][1]=1;
	dp[2][1]=1;
	dp[1][2]=1;
	cin>>a>>b;
	for(int i=1;i<=a;i++)
	{
		for(int j=1;j<=b;j++)
		{
			if(dp[i][j]==0)
			{
				dp[i][j]=dp[i-1][j]+dp[i][j-1];
			}
		}
	}
	cout<<dp[a][b];
	return 0;
}