机器人走方格

拼搏现实的明天。 2021-09-28 19:48 281阅读 0赞

有一个X\*Y的网格，一个机器人只能走格点且只能向右或向下走，要从左上角走到右下角。请设计一个算法，计算机器人有多少种走法。

给定两个正整数int x,int y，请返回机器人的走法数目。保证x＋y小于等于12。

这里采用两种方法实现。默认是3\*3的方格。

public class 机器人走方格 {
        public static void main(String[] args) {
            System.out.println(robotStep(3,3));
            System.out.println(robotStep2(3,3));
        }
        
        /**
         * 递归计算在一个矩形方格内,机器人从左上角到右下角可以行走的方法
         * @param x 行数
         * @param y 列数
         * @return int
         */
        static int robotStep(int x,int y) {
            if(x==1 || y==1) return 1;
            //向下走+向右走的步数
            return  robotStep(x-1,y)+robotStep(x,y-1);
        }
        
        /**
         * O(m+n+n^2),迭代实现
         * @param m
         * @param n
         * @return
         */
        static int robotStep2(int m ,int n) {
            int[][] state = new int[m][n];
            for(int i=0;i<m;i++) state[i][0] = 1;
            for(int i=0;i<n;i++) state[0][i] = 1;
            for(int i=1;i<m;i++) {
                for(int j=1;j<n;j++) {
                    state[i][j] =  state[i-1][j]+state[i][j-1];
                }
            }
            return state[m-1][n-1];
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，281人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法题】机器人走迷宫

机器人走迷宫 [力扣62. 不同路径][62.] ![在这里插入图片描述][947a506a842242e08c4b47b8db227647.png] pa

约定不等于承诺〃/ 2024年03月27日 11:00/ 0 赞/ 46 阅读

相关华为OD机试 - 机器人走迷宫（Java）

题目描述 1. 房间由XY的方格组成，例如下图为6\4的大小。每一个方格以坐标(x，y)描述。 2. 机器人固定从方格(0，0)出发，只能向东或者向北前进。出口固定为

╰+哭是因爲堅強的太久メ/ 2024年03月17日 18:30/ 0 赞/ 16 阅读

相关（每日一练c++）CC182 机器人走方格II

前言 C++是一种计算机高级程序设计语言，由C语言扩展升级而产生，最早于1979年由本贾尼·斯特劳斯特卢普在AT&T贝尔工作室研发。 C++既可以进行C语言的过程化

偏执的太偏执、/ 2023年10月04日 18:03/ 0 赞/ 17 阅读

相关 [蓝桥杯 2020 省 AB1] 走方格——动态规划

题目描述在平面上有一些二维的点阵。这些点的编号就像二维数组的编号一样，从上到下依次为第 1 至第 n 行，从左到右依次为第 1 至第 m 列，每一个点可以用行号和列

Bertha 。/ 2023年09月26日 18:18/ 0 赞/ 82 阅读

相关走方格的方案数（C++牛客网）

解题思路：（1）递归回溯 include<iostream> include<vector> using namespace std;

本是古典何须时尚/ 2022年11月13日 04:18/ 0 赞/ 131 阅读

相关 (动态规划问题)机器人走方格

有一个XxY的网格，一个机器人只能走格点且只能向右或向下走，要从左上角走到右下角。请设计一个算法，计算机器人有多少种走法。给定两个正整数int x,int y，请返回机器人的

迷南。/ 2022年09月28日 11:58/ 0 赞/ 139 阅读

相关 51nod1119 机器人走方格组合数学

M \ N的方格，一个机器人从左上走到右下，只能向右或向下走。有多少种不同的走法？由于方法数量可能很大，只需要输出Mod 10^9 + 7的结果。题目本身很简单，

﹏ヽ暗。殇╰゛Y/ 2022年08月21日 14:49/ 0 赞/ 125 阅读

相关机器人走迷宫

机器人走迷宫 Time Limit: 1000ms Memory limit: 32768K 有疑问？点这里^\_^ 题目描述迷宫对大家来说肯定是很熟悉的东

系统管理员/ 2022年08月18日 02:26/ 0 赞/ 115 阅读

相关机器人走方格

M \ N的方格，一个机器人从左上走到右下，只能向右或向下走。有多少种不同的走法？由于方法数量可能很大，只需要输出Mod 10^9 + 7的结果。 Input 第1行，2个

叁歲伎倆/ 2022年06月12日 10:43/ 0 赞/ 126 阅读

相关机器人走方格

有一个X\Y的网格，一个机器人只能走格点且只能向右或向下走，要从左上角走到右下角。请设计一个算法，计算机器人有多少种走法。给定两个正整数int x,int y，请返回机器人

拼搏现实的明天。/ 2021年09月28日 19:48/ 0 赞/ 282 阅读