后台-插件-广告管理-内容页广告位一(手机)

您现在的位置是:首页 > 开发类 > 游戏开发游戏开发

剑指offer:走方格的方案数_牛客网

2021-06-05 09:12:00游戏开发人已围观

简介文章目录1 题目描述1.1 描述1.2 示例2 解题思路3 代码走方格的方案数_牛客网1 题目描述1.1 描述请计算n*m的棋盘格子(n为横向的格子数,m为竖向的格子数)沿着各自边缘线从左上角走到右下角,总共有多少种走法,要求不能走回头路,即:只能往右和往下走,不能往左和往上走。(本题含有多组样例输入)输入每组样例输入两个正整数n和m,用空格隔开。(1≤n,m≤8)输出每组样例输出一行结果1.2 示例输入2 21 2输出632 解题思路首先

文章目录

  • 1 题目描述
    • 1.1 描述
    • 1.2 示例
  • 2 解题思路
  • 3 代码

走方格的方案数_牛客网

1 题目描述

1.1 描述

  • 请计算n*m的棋盘格子(n为横向的格子数,m为竖向的格子数)沿着各自边缘线从左上角走到右下角,总共有多少种走法,要求不能走回头路,即:只能往右和往下走,不能往左和往上走。(本题含有多组样例输入)

  • 输入

每组样例输入两个正整数n和m,用空格隔开。(1≤n,m≤8)
  • 输出
每组样例输出一行结果

1.2 示例

  • 输入
2 2
1 2
  • 输出
6
3

2 解题思路

  • 首先这道题是一个 n * m 的棋盘格子,只能往下或者往右走,并且这里是沿着边缘线走,而不是在格子中走。
  • 那么我们要求的是什么呢?从左上角走到右下角,那么就是从 (0,0) 移动到 (n,m) 的所有可以到的方案个数。由于只能往下或者往右,那么当走到它上方和左方的时候就只有一种方法可走,那么每个格子的可行方案数就是从 (0,0) 它正上方 (n-1,m) 的个数加上从 (0,0) 它左方 (n,m-1) 的个数。这里有一种特殊情况:当走到第一行(第一列)的时候每次只能向下走(向右走)
  • 那么我们可以用一个二维数组来存储当前点的方案个数,那么我们的数组大小为多少呢?path[n] [m]吗?注意这里的沿着边缘线, n * m 的棋盘格子有 (n+1) * (m+1) 个顶点,所以应该是 path[n+1] [m+1]。
    在这里插入图片描述

3 代码

  • 话不多说,上代码:
import java.util.*;


public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNextInt()) {
            int row = scan.nextInt();//棋盘的行数
            int col = scan.nextInt();//棋盘的列数
            int[][] path = new int[row+1][col+1];
            for (int i = 0; i < row+1; i++) {
                for (int j = 0; j < col+1; j++) {
                    if (i == 0 || j == 0) {//第一行和第一列
                        path[i][j] = 1;
                    }else {
                        path[i][j] = path[i-1][j] + path[i][j-1];
                    }
                }
            }
            System.out.println(path[row][col]);
        }
    }
}
  • 那么我其实不难看出来,我们计算 (n,m) 位置的方案数,其实只需要最后一行的数据。那么我们做一个优化,将二维数组换成一维数组,每次循环更新下一行的值。

  • 这次我们数组大小为 path[col+2] ,首先 col 个格子有 col+1 个顶点,其次我们将 path[0] 空出来就不需要再做 if (i == 0) 这样的判断,并且 path[0] = 0 并不会影响到其他的值。

  • 优化后的代码:

import java.util.*;


public class Main {
	public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNextInt()) {
            int row = scan.nextInt();
            int col = scan.nextInt();
            System.out.println(pathSum(row,col));
        }
    }
    //为了避免浪费空间采用一维数组的方式存储
    public static int pathSum(int row,int col) {
        int[] path = new int[col+2];
        for (int i = 1; i < col+2; i++) {
            path[i] = 1;
        }
        for (int i = 0; i < row; i++) {
            //每一行更新一次数组中的元素,即更新下一行的路径和
            for (int j = 1; j < col+2; j++) {
                path[j] = path[j] + path[j-1];
            }
        }
        return path[col+1];
    }
}

文章来源:https://blog.csdn.net/qq_52574924/article/details/117464709

Tags:动态规划 算法 java 数组 

很赞哦! ()

上一篇:你好!编程!

下一篇:返回列表

后台-插件-广告管理-内容页广告位二(手机)

相关文章

后台-插件-广告管理-内容页广告位三(手机)

随机图文

后台-插件-广告管理-内容页广告位四(手机)

文章评论

留言与评论(共有 0 条评论)
   
验证码:

本栏推荐

站点信息

  • 文章统计60079篇文章
  • 浏览统计4401次浏览
  • 评论统计1个评论
  • 标签管理标签云
  • 统计数据:统计代码
  • 微信公众号:扫描二维码,关注我们