[leetcode 63] 不同路径 II（Python 动态规划+滚动数组优化）

清疚 2023-02-23 08:05 135阅读 0赞

### 目录 ###

*   *  题目描述
     *  解题思路
     *  代码实现
     *  Tips

## 题目描述 ##

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？  
![在这里插入图片描述][20200706094242277.png]  
网格中的障碍物和空位置分别用 1 和 0 来表示。

说明：m 和 n 的值均不超过 100。

示例 1:

> 输入: \[ \[0,0,0\], \[0,1,0\], \[0,0,0\] \]  
> 输出: 2  
> 解释:  
> 3x3 网格的正中间有一个障碍物。  
> 从左上角到右下角一共有 2 条不同的路径：
> 
> 1.  向右 -> 向右 -> 向下 -> 向下
> 2.  向下 -> 向下 -> 向右 -> 向右

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/unique-paths-ii

## 解题思路 ##

我们用  f ( i , j ) f(i, j) f(i,j) 来表示从坐标  ( 0 , 0 ) (0, 0) (0,0) 到坐标  ( i , j ) (i, j) (i,j) 的路径总数， u ( i , j ) u(i, j) u(i,j) 表示坐标  ( i , j ) (i, j) (i,j) 是否可行，如果坐标  ( i , j ) (i, j) (i,j) 有障碍物， u ( i , j ) = 0 u(i, j) = 0 u(i,j)=0，否则  u ( i , j ) = 1 u(i, j) = 1 u(i,j)=1。

因为`机器人每次只能向下或者向右移动一步`，所以 ( 0 , 0 ) (0, 0) (0,0) 到坐标  ( i , j ) (i, j) (i,j) 的路径总数的值只取决于从坐标  ( 0 , 0 ) (0, 0) (0,0) 到坐标  ( i − 1 , j ) (i - 1, j) (i−1,j) 的路径总数和从坐标  ( 0 , 0 ) (0, 0) (0,0) 到坐标  ( i , j − 1 ) (i, j - 1) (i,j−1) 的路径总数，即  f ( i , j ) f(i, j) f(i,j) 只能通过  f ( i − 1 , j ) f(i - 1, j) f(i−1,j) 和  f ( i , j − 1 ) f(i, j - 1) f(i,j−1) 转移得到。

当坐标  ( i , j ) (i, j) (i,j) 本身有障碍的时候：任何路径都到到不了  f ( i , j ) f(i, j) f(i,j)，此时  f ( i , j ) = 0 f(i, j) = 0 f(i,j)=0。  
当坐标  ( i , j ) (i, j) (i,j) 没有障碍的时候：如果坐标  ( i − 1 , j ) (i - 1, j) (i−1,j) 没有障碍，那么就意味着从坐标  ( i − 1 , j ) (i - 1, j) (i−1,j) 可以走到  ( i , j ) (i, j) (i,j) ，即  ( i − 1 , j ) (i - 1, j) (i−1,j) 位置对  f ( i , j ) f(i, j) f(i,j) 的贡献为  f ( i − 1 , j ) f(i - 1, j) f(i−1,j) ；同理，当坐标  ( i , j − 1 ) (i, j - 1) (i,j−1) 没有障碍的时候， ( i , j − 1 ) (i, j - 1) (i,j−1) 位置对  f ( i , j ) f(i, j) f(i,j) 的贡献为  f ( i , j − 1 ) f(i, j - 1) f(i,j−1) 。

综上所述，我们可以得到这样的动态规划转移方程：  
 f ( i , j ) = \{ 0 , u ( i , j ) = 0 f ( i − 1 , j ) + f ( i , j − 1 ) , u ( i , j ) ≠ 0 f(i, j)=\\left\\\{\\begin\{aligned\} 0, & u(i, j)=0 \\\\ f(i-1, j)+f(i, j-1), & u(i, j) \\neq 0 \\end\{aligned\}\\right. f(i,j)=\{ 0,f(i−1,j)\+f(i,j−1),u(i,j)=0u(i,j)=0  
由于这里  f ( i , j ) f(i, j) f(i,j) 只与  f ( i − 1 , j ) f(i - 1, j) f(i−1,j) 和  f ( i , j − 1 ) f(i, j - 1) f(i,j−1) 相关，我们可以运用`滚动数组思想`把空间复杂度优化称  O ( m ) O(m) O(m)。

> 滚动数组思想是一种常见的动态规划优化方法，在题目中已经多次使用到，例如「剑指 Offer 46. 把数字翻译成字符串」、「70. 爬楼梯」等，当定义的状态在动态规划的转移方程中只和某几个状态相关的时候，就可以考虑这种优化方法，目的是给空间复杂度「降维」。

**- 复杂度分析**

*  时间复杂度： O ( n m ) O(nm) O(nm)，其中  n n n 为网格的行数， m m m 为网格的列数。我们只需要遍历所有网格一次即可。
 *  空间复杂度： O ( m ) O(m) O(m)。利用滚动数组优化，我们可以只用  O ( m ) O(m) O(m) 大小的空间来记录当前行的  f f f 值。

## 代码实现 ##

class Solution(object):
        def uniquePathsWithObstacles(self, obstacleGrid):
            """
            :type obstacleGrid: List[List[int]]
            :rtype: int
            """
            m = len(obstacleGrid)
            n = len(obstacleGrid[0])
            dp = [1] + [0]*(n-1)
            for i in range(m):
                for j in range(n):
                    if j == 0:
                        dp[j] = 0 if obstacleGrid[i][j] else dp[j]
                    else:
                        dp[j] = 0 if obstacleGrid[i][j] else dp[j] + dp[j-1]
            return dp[-1]

--------------------

## Tips ##

怎么想到用动态规划来解决这个问题呢？我们需要从问题本身出发，寻找一些有用的信息，例如本题中：

*   ( i , j ) (i, j) (i,j) 位置只能从  ( i − 1 , j ) (i - 1, j) (i−1,j) 和  ( i , j − 1 ) (i, j - 1) (i,j−1) 走到，这样的条件就是在告诉我们这里转移是 `无后效性` 的， f ( i , j ) f(i, j) f(i,j) 和任何的  f ( i ′ , j ′ ) ( i ′ > i , j ′ > j ) f(i', j')(i' > i, j' > j) f(i′,j′)(i′>i,j′>j) 无关。
 *  动态规划的题目分为两大类，一种是`求最优解类`，典型问题是背包问题，另一种就是`计数类`，比如这里的统计方案数的问题，它们都存在一定的`递推性质`。前者的递推性质还有一个名字，叫做 `最优子结构` ——即**当前问题的最优解取决于子问题的最优解，后者类似，当前问题的方案数取决于子问题的方案数**。所以在遇到求方案数的问题时，我们可以往动态规划的方向考虑。  
    通常如果我们察觉到了这两点要素，这个问题八成可以用动态规划来解决。

根据官方题解总结。

--------------------

A u t h o r : C h i e r Author: Chier Author:Chier

[20200706094242277.png]: https://img-blog.csdnimg.cn/20200706094242277.png