当前位置:网站首页>力扣62 不同路径(从矩阵左上到右下的所有路径数量) (动态规划)
力扣62 不同路径(从矩阵左上到右下的所有路径数量) (动态规划)
2022-07-07 01:41:00 【裴南苇_】
今天遇到一道个人认为很有价值的动态规划问题。从这道题里,个人感觉对动态规划有了更深刻的了解,大家可以看看对自己又没有帮助。
先看题目:
一个机器人位于一个 m x n 网格的左上角,机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角问总共有多少条不同的路径?
示例
输入:m = 3, n = 2
输出:3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
解答:
由题目得知,每一次只能向下或者向右移动
由此我们推知 ===》 到达一个格子的路径数量,由它左边格子和上边格子所决定
由此我们推知 ===》 这里可以使用动态规划的思想来解决
由此动态方程 ===》 dp[i][j] = dp[i-1][j] + dp[i][j-1]
至此,我们已经解决一半的问题了,然后我们再思考第一列和第一行,由于每一次只能向下或者向右移动,所以第一行的每个格子都只能由它左边的格子向右移动而来, 所以第一行dp[0][j] 都应该为1,第一列格子同理。
至此分析结束,列出代码
public int uniquePaths(int m, int n) {
int[][] dp = new int [m][n];
for(int i=0;i<n;i++){
dp[0][i] = 1;
}
for(int i=0;i<m;i++){
dp[i][0] = 1;
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
dp[i][j] = dp[i-1][j]+dp[i][j-1];
}
}
return dp[m-1][n-1];
}
好了,这次的文章就到这里,喜欢的同学可以点赞收藏,遇到问题,可以评论,或者留言,我一定会第一时间给到回馈,感谢观看!!
注:本文为本人学习时心得分享,有讲错或者需要改正的地方,请指正,我会虚心接受
边栏推荐
- window下面如何安装swoole
- 当我们谈论不可变基础设施时,我们在谈论什么
- Oracle迁移中关于大容量表使用数据泵(expdp、impdp)导出导入容易出现的问题和注意事项
- Understand the deserialization principle of fastjson for generics
- ST表预处理时的数组证明
- 【FPGA教程案例14】基于vivado核的FIR滤波器设计与实现
- 高并发大流量秒杀方案思路
- Array proof during st table preprocessing
- Change the original style of UI components
- 360织语发布7.0新品 为党政军、央国企打造专属“统一数字工作空间”
猜你喜欢
Peripheral driver library development notes 43: GPIO simulation SPI driver
693. Travel sequencing
DC-7靶机
Financial risk control practice - decision tree rule mining template
How to keep accounts of expenses in life
Jmeter自带函数不够用?不如自己动手开发一个
JVM命令之 jstack:打印JVM中线程快照
Jinfo of JVM command: view and modify JVM configuration parameters in real time
JVM monitoring and diagnostic tools - command line
When we talk about immutable infrastructure, what are we talking about
随机推荐
解决pod install报错:ffi is an incompatible architecture
Rk3399 platform development series explanation (WiFi) 5.52. Introduction to WiFi framework composition
Jmeter自带函数不够用?不如自己动手开发一个
980. Different path III DFS
安装mongodb数据库
Sequential storage of stacks
MySQL performance_ Schema common performance diagnosis query
Developers don't miss it! Oar hacker marathon phase III chain oar track registration opens
QT console output in GUI applications- Console output in a Qt GUI app?
New Year Fireworks code plus copy, are you sure you don't want to have a look
【FPGA教程案例14】基于vivado核的FIR滤波器设计与实现
Apple CMS V10 template /mxone Pro adaptive film and television website template
Vscode for code completion
You don't know the complete collection of recruitment slang of Internet companies
开发者别错过!飞桨黑客马拉松第三期链桨赛道报名开启
JVM命令之 jinfo:实时查看和修改JVM配置参数
POI excel export, one of my template methods
改变ui组件原有样式
360 Zhiyu released 7.0 new products to create an exclusive "unified digital workspace" for the party, government and army, and central and state-owned enterprises
谷歌 Chrome 浏览器发布 103.0.5060.114 补丁修复 0-day 漏洞