这题，用dfs百分百超时

本题求的是路径数，并且限制了只能向下走和向右走

首先考虑2x2的格子，对于右下角的格子，路径就是右->下和下->右，恰好就是前往终点格子上面与左边的路径之和

再考虑3x3的格子，发现前往最上边的任意格子或最左边的任意格子，路径都是只有一条（这是由只能向下和向右走决定的）

而其他格子的路径数，恰好也是前往这个格子上面与左面的路径之和

故使用动态规划，dp[i][j]表示前往(i,j)这个格子的总路径数

#include <bits/stdc++.h>
using namespace std;

const int maxn = 105;

long long dp[maxn][maxn];
bool vis[maxn][maxn];


int main()
{
	memset(dp,1,sizeof(dp));
	memset(vis,false,sizeof(vis));
	long long m,n;
	cin >> m >> n;
	for(long long i = 0;i < m;++i)
	{
		for(long long j = 0;j < n;++j)
		{
			if(i - 1 < 0 || j - 1 < 0)// 最上边 最左边
			{
				dp[i][j] = 1;
				continue;
			}
			else
			{
				dp[i][j] = dp[i-1][j] + dp[i][j-1];
			}
		}
	
	}
	cout << dp[m-1][n-1] << endl;
	return 0;
}