题意:n*m的矩阵,从左上角到右下角每次只能向右一步或者向下一步,问共有多少种走法。
从左上角到右下角一共要走n+m-2步,这其中一定有n-1步是必须要向下走的,但是什么时候向下走是不知道的。c[n+m-2][n-1]代表的意思就是n*m矩阵的走法。
用递推公式:c[n][m]=c[n-1][m]+c[n-1][m-1];
memset(c,0,sizeof(c));//清零很重要 c[0][0]=1;//很重要; for(int i=1; i<=2000; i++)//从1开始 { c[i][0]=1;//很重要,因为它也是一种情况,会影响后面的递推结果; for(int j=1; j<=1000; j++)//从1开始到最大的n; { c[i][j]=(c[i-1][j]+c[i-1][j-1])%1000000007; } }
AC代码:
#include<iostream> #include<queue> #include <string.h> #include <stdio.h> #include <stdlib.h> #include <math.h> #define INF 0x3f3f3f3f using namespace std; int c[2010][2000]; int main() { int n,m; memset(c,0,sizeof(c)); c[0][0]=1; for(int i=1; i<=2000; i++) { c[i][0]=1; for(int j=1; j<=1000; j++) { c[i][j]=(c[i-1][j]+c[i-1][j-1])%1000000007; } } while(~scanf("%d%d",&n,&m)) { if(n==0||m==0) { printf("0 "); continue; } printf("%d ",c[n+m-2][n-1]); } return 0; }