机器人走方格

M * N的方格，一个 机器人 从左上走到右下，只能向右或向下走。有多少种不同的走法？由于方法数量可能很大，只需要输出Mod 10^9 + 7的结果。  Input  第1行，2个数M,N，中间用空格隔开。（2 <= m,n <= 1000)  Output  输出走法的数量。  Input示例  2 3  Output示例 

3

#include <stdio.h> #include <string.h> #define _MOD 1000000007 int map[1001][1001]; //存储数据 int path(int M, int N) { if (map[M][N])//记忆化搜索 ，内存换时间 { return map[M][N]; } else if (M == 1 || N == 1) { map[M][N] = 1; return map[M][N]; } map[M][N] = (path(M - 1, N) + path(M, N - 1)) % _MOD; return map[M][N]; } int main(int argc, const char * argv[]) { int M, N, ans; while (~scanf("%d %d", &M, &N)) { memset(map, 0, sizeof(int) * 1001 * 1001); ans = path(M, N); printf("%d\n", ans); } return 0; }