题目描述

基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题 收藏 关注
M * N的方格，一个机器人从左上走到右下，只能向右或向下走。有多少种不同的走法？由于方法数量可能很大，只需要输出Mod 10^9 + 7的结果。
Input
第1行，2个数M,N，中间用空格隔开。（2 <= m,n <= 1000)
Output
输出走法的数量。
Input示例
2 3
Output示例
3

解题思想

/*
本题有三种解法，依次是
1.普通迷宫解法，即dfs
这种方法会超时，不在此叙述
2.动态规划
dp[i][j] = dp[i-1][j] + dp[i][j-1]
dp[i][j]表示从(0,0)走到(i,j)所用的方法数
3.排列组合+乘法逆元
首先乘法逆元是：是将2个非常大的数(a/b)相除，然后在对p取模，
由于除数或者被除数太大，需要边乘边取模，最后就变成了
(a%p)/(b%p) %p ,然而并不等于(a//b)%p,所以就需要将除法转换成为乘法
然后排列组合求c(m+n-2,m-1)或者c(m+n-2,n-1)
为什么求这个组合呢？
我觉得我也没理解。求大神指点
*/

代码

// import java.util.Scanner;
// public class Main{
// static int count = 0;
// static int[][] map = null;
// static int[][] point = {{0,1},{1,0}};
// static int m , n;
// static final int p = 1000000007;
// public static void main(String[] args){
// Scanner sc = new Scanner(System.in);
// m = sc.nextInt();
// n = sc.nextInt();
// //init
// map = new int[m][n];
// // vis = new int[m][n];
// dfs(0,0);
// System.out.println(count);
// }
// public static void dfs(int i, int j){
// if(i==m-1 && j ==n-1){
// count += 1 % p;
// return;
// }else{
// for(int k=0; k<2; ++k){
// int dx = i + point[k][0];
// int dy = j + point[k][1];
// if(dx>=0&&dx<m && dy>=0&& dy<n)
// if(map[dx][dy]==0){
// map[dx][dy] = 1;
// dfs(dx,dy);
// map[dx][dy] = 0;
// }
// }
// }

// }
// }
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[][] dp = new int[m][n];
        for(int i=0; i<m; ++i)
          for(int j=0; j<n; ++j){
              if(i==0 || j==0)
                 dp[i][j] = 1;
              else{
                  dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007;
              }
          }
           System.out.println(dp[m-1][n-1]); 
    }
}