小D從家到學校的道路結構是這樣的：由n條東西走向和m條南北走向的道路構成了一個n*m的網(wǎng)格，每條道路都是單向通行的（只能從北向南，從西向東走）
已知小D的家在網(wǎng)格的左上角，學校在網(wǎng)格的右下角。
問小D從他的家到學校一共有多少種不同的上學路線。

輸入
兩個正整數(shù)n和m，意義如題目所述。
輸出
小D上學路線數(shù)量，結果對1000000007取余。
樣例輸入
3 4
樣例輸出
10
100%的數(shù)據(jù)，n,m≤1000

這個題，看到的第一思路就是組合數(shù)。
因為從頭到學校需要n+m-2步 ，將向右走看成一種方案有m-1，向下走看成一種方案n-1，那么C（n+m-2,m-1）就是答案了。聽起來很簡單，不過還要取余。。。很明顯階乘肯定爆掉了，每次對階乘取余不符合除法取余規(guī)則。。菜雞的我還沒學會除法取余（逃）所以這種方法寫完交上去WA了幾次就放棄了。經(jīng)大佬啟發(fā) ，最后的方案數(shù)不就等于上兩個格方案數(shù)相加嘛，這樣不斷遞推，就可以得到最后的方案數(shù)，算是能a掉了吧~

先將邊路變成1，因為到邊路的方案只有一種所以都設為1，再從[2][2]開始遍歷
將能移動到它的上兩個方格方案數(shù)相加，一直到終點，可得答案。

#include<cstdio>int vis[2000][2000],ans;int main() {int n,m;scanf("%d %d",&n,&m);for(int i=1;i<=n;i++)vis[i][1]=1;for(int i=1;i<=m;i++)vis[1][i]=1;for(int i=2;i<=n;i++)for(int j=2;j<=m;j++)vis[i][j]=(vis[i-1][j]+vis[i][j-1])%1000000007;ans=(vis[n][m])%1000000007;printf("%d",ans);return 0; }

總結

以上是生活随笔為你收集整理的背着书包去上学~的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。