解题关键：
1、此题用dp的方法可以看出，dp矩阵为杨辉三角，通过总结，可以得出 答案的解为$C_{n + m - 2}^{n - 1}$
2、此题可用组合数学的思想考虑，总的步数一共有$n+m-2$步，在这所有的步数中，需要选择向下走的步数的位置，由此可得，答案的解为：$C_{n + m - 2}^{n - 1}$
此题即可转化为大组合数取模问题；
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int mod=1e9+7; 5 ll mod_pow(ll x,ll n,ll p){ 6 ll res=1; 7 while(n){ 8 if(n&1) res=res*x%p; 9 x=x*x%p; 10 n>>=1; 11 } 12 return res; 13 } 14 ll comb(ll n,ll m,ll p){ 15 if(n==m) return 1; 16 if(n<m) return 0; 17 if(m>n-m) m=n-m; 18 19 ll tn=1,tm=1; 20 while(m){ 21 tn=tn*n%p; 22 tm=tm*m%p; 23 n--,m--; 24 } 25 return (tn*mod_pow(tm,p-2,p)+mod)%mod; 26 } 27 int main(){ 28 int n,m; 29 cin>>n>>m; 30 ll ans=comb(n+m-2,n-1,mod); 31 cout<<ans<<endl; 32 return 0; 33 }
如下为dp的解法
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int mod=1e9+7; 5 int dp[1002][1002]; 6 int main(){ 7 int n,m; 8 cin>>n>>m; 9 for(int i=0;i<=1000;i++){ 10 dp[1][i]=dp[i][1]=1; 11 } 12 for(int i=2;i<=m;i++){ 13 for(int j=2;j<=n;j++){ 14 dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod; 15 } 16 } 17 cout<<dp[m][n]<<endl; 18 }