题解 | #走方格的方案数#

采用动态规划进行求解！

因为只能够向下或者是向右走，所以对第(m,n)个格子的总走法等价于来自于左边的走法数加上上边的走法数之和！

设dp[m][n]为第(m,n)个格子的走法数，其等于dp[m][n]=dp[m-1][n]+dp[m][n-1]，
初始化：第一行和第一列的总走法等于1！

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        while(in.hasNext()){
            int m=in.nextInt();//行数
            int n=in.nextInt();//列数
            int[][] dp=new int[m+1][n+1];//dp[m][n]表示m*n个有多少种走法！
            dp[0][0]=1;
            for(int i=1;i<=n;i++){//将第一行初始化为1
                dp[0][i]=1;
            }
            for(int j=1;j<=m;j++){//将第一列初始化为1
                dp[j][0]=1;
            }

            for(int i=1;i<=m;i++){
                for(int j=1;j<=n;j++){
                    //因为到达第m*n个位置只能够来自上方或或者是左方！
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
            }


            System.out.println(dp[m][n]);
        }
    }


}