题解 | #走方格的方案数#
走方格的方案数
http://www.nowcoder.com/practice/e2a22f0305eb4f2f9846e7d644dba09b
采用动态规划进行求解!
因为只能够向下或者是向右走,所以对第(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]); } } }