$\it{***方法一(排列组合)***}$
要点:
1.问题数学模型化
,由于合计移动n+m次且只能右移(总m次)或下移(总n次),即组合数问题$C^m_{n+m}=\dfrac{(m+n)!}{m!\cdot n!}$,简化为阶乘问题
2.注意返回值数值范围
,返回值为int类型时会爆,扩成long int类型
#include<bits/stdc++.h>
using namespace std;
//每次只能往右或者往下走,即组合数问题,细划为阶乘问题
long int foo(int n)
{
if(n==1) return 1;
return n*foo(n-1);
}
int main()
{
int n,m;
cin>>n>>m;
cout<<foo(n+m)/(foo(n)*foo(m));
return 0;
}
$\it{***方法二(简单DFS)***}$
图解:
#include<bits/stdc++.h>
using namespace std;
int ans;
int n,m;
void dfs(int x,int y)
{
if(x==n&&y==m) ans++;
else
{
if(y<m) dfs(x,y+1);
if(x<n) dfs(x+1,y);
}
}
int main()
{
cin>>n>>m;
dfs(0,0);
cout<<ans<<endl;
return 0;
}