上学路线

上学路线

题目描述：
小D从家到学校的道路结构是这样的：由n条东西走向和m条南北走向的道路构成了一个n*m的网格，每条道路都是单向通行的（只能从北向南，从西向东走）。已知小D的家在网格的左上角，学校在网格的右下角。问小D从他的家到学校一共有多少种不同的上学路线。
输入：
两个正整数n和m，意义如题目所述。
输出：
小D上学路线数量，结果队1000000007取余。
样例输入：
4
样例输出：
10
提示：100%的数据，n,m≤1000

（感谢我的神奇队友，要不然这道水题都不知道要卡多久）
此题最大的坑就在于数据范围，太大了，传统的排列组合算法是这样的：

int sum(int m, int n)//横m纵n，计算的是C(mn-2,n-1)
{int  = n  m - 2;int K = n - 1;double ans = 1.0;for (int i = 1; i <= n - 1; i){ans = ans * ( - K  i) / i;}return (int)ans;
}

但1000 1000真的太大了，导致long long都放不下，只好放弃这种做法（其实高精度求余应该也行，但我懒得敲）
于是，这种递归的做法就出现了：

int sum(int m,int n)//横m纵n，计算的是C(mn-2,n-1)
{if(m==1||n==1)return 1;int ans=sum(m-1,n)sum(m,n-1);return ans;
}

结果……超时？！
好吧，这就是我队友神奇的地方了，我当时是没有想到啊，拿数组优化一下就过了。AC代码如下：

#include<bits/stdc.h>
using namespace std;
long long sum[1001][1001]={0};//数组太大，放里面会编译不出来
int main()
{int m,n;scanf(%d%d,&m,&n);for(int i=1; i<=m; i)//避免了递归，这样复杂度最高1e6，也就不会T了{for(int j=1; j<=n; j){if(i==1||j==1) sum[i][j] = 1;else  sum[i][j] =(sum[i-1][j]sum[i][j-1])%1000000007;//每一步都取余，避免最后放不下}}long long ans=sum[m][n];cout<<ans<<endl;return 0;
}