一只饥饿的小蚂蚁外出觅食，幸运的的小蚂蚁发现了好多食物。
但是这些食物位于一个N∗M的方格魔法阵的右下角，而小蚂蚁位于方格法阵的左上角。
并且小蚂蚁被施展了魔法，它只能向下或者向右走。
请你帮助小蚂蚁计算一下，它一共有多少条路可以走到有食物的方格。
输入格式
多组输入，
每一组两个正整数N， M （N,M≤30）。表示一个方格魔法阵。
输出格式
一个整数表示一共有多少条路。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
ll dp[50][50];
int d[2][2]={{1,0},{0,1}};
int n,m;
ll dfs(int x,int y){
if(dp[x][y]) return dp[x][y];
for(int i=0;i<2;i++){
int dx=x+d[i][0];
int dy=y+d[i][1];
if(dx>=1&&dy>=1&&dx<=n&&dy<=m){
dp[x][y]+=dfs(dx,dy);
}
}
return dp[x][y];
}
int main(){
while(cin>>n>>m){
memset(dp,0,sizeof(dp));
dp[n][m]=1;
cout<<dfs(1,1)<<endl;
}
return 0;
}
思路2 直接动态规划（不太会）类似于矩阵取数，把max替换为sum就可以了，（一般求方案的都是将max替换为sum）
AC代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
ll dp[50][50];
int n,m;
int main(){
while(cin>>n>>m){
dp[1][1]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
dp[i][j] +=dp[i-1][j]+dp[i][j-1];
cout<<dp[n][m]<<endl;
}
return 0;
}
