机器人走方格

拼搏现实的明天。 2021-09-28 19:48 309阅读 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 条评论，309人围观）

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

相关阅读

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

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

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

相关 51nod 1119 机器人走方格 V2 求大组合取模--逆元

[1119 机器人走方格 V2][1119 _ V2] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 10 [1119 _ V2]:

迈不过友情╰/ 2024年02月17日 20:36/ 0 赞/ 36 阅读

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

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

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

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

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

妖狐艹你老母/ 2023年10月04日 18:03/ 0 赞/ 38 阅读

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

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

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

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

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

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

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

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

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

相关机器人走迷宫

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

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

相关机器人走方格

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

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

相关机器人走方格

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

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