本文转载自微信公众号「我好困啊」,作者我好困啊。转载本文请联系我好困啊公众号。
10年的桑珠孜网站建设经验,针对设计、前端、开发、售后、文案、推广等六对一服务,响应快,48小时及时工作处理。成都全网营销推广的优势是能够根据用户设备显示端的尺寸不同,自动调整桑珠孜建站的显示方式,使网站能够适用不同显示终端,在浏览器中调整网站的宽度,无论在任何一种浏览器上浏览网站,都能展现优雅布局与设计,从而大程度地提升浏览体验。创新互联从事“桑珠孜网站设计”,“桑珠孜网站推广”以来,每个客户项目都认真落实执行。
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
图片来源leetcode
示例1:
- 输入:m = 3, n = 7
- 输出:28
示例2:
- 输入:m = 3, n = 2
- 输出:3
- 解释:
- 从左上角开始,总共有 3 条路径可以到达右下角。
- 1. 向右 -> 向下 -> 向下
- 2. 向下 -> 向下 -> 向右
- 3. 向下 -> 向右 -> 向下
提示:
利用动态规划算法
1.定义状态f[i][j]为到达(i,j)位置的路径条数
2.f[0][0] = 1,那么最终m*n的表格,到达右下角的路径条数即为f[m-1][n-1]中的值
3.每次移动情况,如果当前位置:
向下:f[i][j] = f[i-1][j]
向右: f[i][j] = f[i][j-1]
向下,向右:f[i][j] = f[i-1][j]+f[i][j-1]
如果你还不理解的话,观看一下流转图:
以2*2的网格为例
说明,从f[0][0]出发,那么开始时,节点f[0][0]=1,
节点f[0][1]只能由于f[0][0]向右移动得到,即 f[0][1]=f[0][0]
节点f[1][0]同理,只能f[0][0]下移得到。即 f[1][0]=f[0][0]
节点f[1][1],可以由于f[0][1]向下移动,f[1][0]向右移动。两种移动方式得到。即:f[1][1] = f[0][1] + f[1][0]
最后,f[m-1][n-1],右下角的位置即为最终结果
如果你还不理解的话,建议你手动画一下2*3的表格移动状态的转移过程。
代码实现
- 1func uniquePaths(m int, n int) int {
- 2 f := make([][]int,m)
- 3 for i:= range f{
- 4 f[i] = make([]int,n)
- 5 }
- 6 f[0][0] = 1
- 7 for i:=0;i
- 8 for j:=0;j
- 9 if i>0 && j>0 { //可以向下,向右移动
- 10 f[i][j] = f[i-1][j] + f[i][j-1]
- 11 }else if i>0 { //可以向下移动
- 12 f[i][j] = f[i-1][j]
- 13 }else if j>0 { //可以向右移动
- 14 f[i][j] = f[i][j-1]
- 15 }
- 16 }
- 17 }
- 18 //循环结束后,走到了终点
- 19 return f[m-1][n-1]
- 20}
复杂度分析
网页标题:一篇搞定动态规划之不同路径
文章起源:http://www.shufengxianlan.com/qtweb/news24/89474.html
网站建设、网络推广公司-创新互联,是专注品牌与效果的网站制作,网络营销seo公司;服务项目有等
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联