机器人走方格
一、问题:
有一个X*Y的网格,一个机器人只能走格点且只能向右或向下走,要从左上角走到右下角。 请设计一个算法,计算机器人有多少种走法。 给定两个正整数int x,int y,请返回机器人的走法数目,保证x+y小于等于12。
二、思路:
思考这类看起来很复杂的问题,实际上就越有规律可循,我们先列举一些简单的情况,再由简到繁,逐步得出结果,逐步发现规律。就是说先解决简单情况下的问题,然后再推广到复杂情况下的问题。就比如这道题目,先假如只有1个格子,那很明显只有一种走法,那么我们再去画 1 * 2,2 * 1,1 * 3,3 * 1,也只有1种走法,再去画2 * 2 的方格,发现有两种走法了。
当我们处于2 * 2的方格的时候我们可以首先往右走一个方格,那么此时我们处于两行一列的状态,我们也可以往下走一个方格那么我们处于一行两列的情况那么1 * 2与2 * 1的走法我们原来是知道的,所以把这两种走法加起来就得到了2 * 2 方格的走法,也就是两种走法。
当我们处于2 * 3的方格的时候我们可以首先往右走一个方格,那么此时我们处于两行两列的状态,我们也可以往下走一个方格那么我们处于一行三列的情况那么2 * 2与1 * 3的情况我们原来是知道的,所以把这两种走法加起来就得到了2 * 3 方格的走法总共有3种走法,依次类推
于是我们根据分析就可以得出递推式f(x , y) = f(x - 1, y) + f(x , y - 1)(因为只能向右走和向下走)
所以我们可以使用递归的方式来解决这个问题,其次我们也可以使用迭代(递推)的方式来解决,因为涉及到两个变量都在变化,使用一维的变量是不能够保存的,所以要使用二维的数据结构:二维数组来保存从起始点到某一点的走法,比如说a[2][3]=3,表示机器人到这一个点总共有3种走法。
使用递归的话就相当于一种富人的思想,把什么都交给手下人去做,自己只负责合并结果,代码很简洁。而迭代(递推)相当于打工者的思想,一步步根据自己的分析得出想要的结果,代码相对来说比递归要复杂一点。
三、代码:
1 public class 机器人走格子 { 2 3 public static void main(String[] args) { 4 System.out.println(solve(3, 3)); // 输出 6 5 System.out.println(solve1(3, 3)); // 输出 6 6 } 7 8 /** 9 * 递归形式 10 */ 11 static int solve(int x,int y){ 12 if( x==1 || y==1 ) return 1; 13 return solve(x-1, y)+solve(x, y-1); 14 } 15 16 /** 17 * 迭代形式 18 */ 19 static int solve1(int m,int n){ 20 int [][]state = new int[m+1][n+1]; 21 for (int i = 1; i <= n; i++) { 22 state[1][i] = 1; 23 } 24 for (int i = 1; i <= m; i++) { 25 state[i][1] = 1; 26 } 27 for (int i = 2; i <=m ; i++) { 28 for (int j = 2; j <=n ; j++) { 29 state[i][j] = state[i][j-1] + state[i-1][j]; 30 } 31 } 32 return state[m][n]; 33 } 34 35 }
四、结果:
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的