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

走方格的方案数

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]);
        }
    }


}
全部评论

相关推荐

高斯林的信徒:问你有没有保底,好人啊,就差把这是kpi面告诉你了
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务