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

本文转载自微信公众号「我好困啊」，篇搞作者我好困啊。定动转载本文请联系我好困啊公众号。态规

题目说明

一个机器人位于一个 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<m;i++ {   8        for j:=0;j<n;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)