一篇搞定动态规划之不同路径

本文转载自微信公众号「我好困啊」，作者我好困啊。转载本文请联系我好困啊公众号。

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 <= m, n <= 100
• 题目数据保证答案小于等于 2 * 109

解题思路

利用动态规划算法

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}
 
 
 
 

复杂度分析

• 时间复杂度：O(m*n)
• 空间复杂度: O(m*n)

名称栏目：一篇搞定动态规划之不同路径
网站路径：http://www.zyruijie.cn/qtweb/news16/7216.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联