每日一道算法之--不同路径

动态规划

Word count: 1.2kReading time: 5 min

 2020/04/01   Share

不同路径

力扣第62题 : https://leetcode-cn.com/problems/unique-paths/

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

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

问总共有多少条不同的路径？

示例 1:

输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。

向右 -> 向右 -> 向下
向右 -> 向下 -> 向右
向下 -> 向右 -> 向右

示例 2:

输入: m = 7, n = 3
输出: 28

动态规划

我们可以假设dp[row][col]是到达第row行第col列的最多可能,那么达到第row行第col列只有两种可能

第row行col- 1列从左边向右移动一位
第row- 1行col列从上到下移动一位

所以状态转移方程为:

dp[row][col] = dp[row][col - 1] + dp[row - 1][col]

注意，对于第一行 dp[0][j]，或者第一列 dp[i][0]，由于都是在边界，所以只能为 1

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 边界处只能为1
        dp = [[1]*n] + [[1]+[0] * (n-1) for _ in range(m-1)]
        print(dp)
        #print(dp)
        for row in range(1, m):
            for col in range(1, n):
                dp[row][col] = dp[row-1][col] + dp[row][col-1]
        return dp[-1][-1]

复杂度分析

时间复杂度：O(m*n),每一种可能都要遍历到

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

优化动态规划

可以发现二维数组占用了太多内存,分析题目发现,其实每一行的子问题只和最后一个结果相关,所以可以将二维数组简化为一维数组

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        cur = [1] * n
        for row in range(1, m):
            for col in range(1, n):
                cur[col] += cur[col - 1]
        return cur[-1]

空间复杂度可以降为 O(n)

不同路径II

力扣第63题 : https://leetcode-cn.com/problems/unique-paths-ii/

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

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

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

示例 1:

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

向右 -> 向右 -> 向下 -> 向下
向下 -> 向下 -> 向右 -> 向右

动态规划

这题和上面唯一的区别就是有了障碍物,这样我们就需要判断是否存在障碍物了,而且边界也要判断。

最初的版本

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        rows = len(obstacleGrid)
        cols = len(obstacleGrid[0])
        dp = [1] + [0]* (cols - 1)
        for row in range(rows):
            for col in range(cols):
                if obstacleGrid[row][col] == 1:
                    dp[col] = 0
                else:
                    dp[col] += dp[col - 1]
        return dp[-1]

这里会出现一个问题,就是当col 为 0 时, col - 1 为 -1 ,这样会取到了倒数第一个数据,从而造成错误

改进版本

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        rows = len(obstacleGrid)
        cols = len(obstacleGrid[0])
        # 在最后在加一个元素0,就可以解决边界问题
        dp = [1] + [0]* cols
        for row in range(rows):
            for col in range(cols):
                if obstacleGrid[row][col] == 1:
                    dp[col] = 0
                else:
                    dp[col] += dp[col - 1]
        return dp[-2]

力扣题解

class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])

        ＃如果起始单元格有障碍物，则只需返回即可
        ＃没有到达目的地的路径
        if obstacleGrid[0][0] == 1:
            return 0

       ＃到达起始像元的方式数量为 1
        obstacleGrid[0][0] = 1

        ＃填充第一列的值
        for i in range(1,m):
            obstacleGrid[i][0] = int(obstacleGrid[i][0] == 0 and obstacleGrid[i-1][0] == 1)

       ＃填充第一行的值
        for j in range(1, n):
            obstacleGrid[0][j] = int(obstacleGrid[0][j] == 0 and obstacleGrid[0][j-1] == 1)

        ＃从cell（1,1）开始填充值
        ＃到达单元格[i] [j] =单元格[i-1] [j] +单元格[i] [j-1]的方式数量
        ＃即从上方和左侧。
        for i in range(1,m):
            for j in range(1,n):
                if obstacleGrid[i][j] == 0:
                    obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]
                else:
                    obstacleGrid[i][j] = 0

        ＃返回值存储在最右边的最底部单元格中。 那是目的地。
        return obstacleGrid[m-1][n-1]

复杂度分析

时间复杂度： O(M×N) 。长方形网格的大小是 M×N，而访问每个格点恰好一次。

空间复杂度： O(1)。我们利用 obstacleGrid 作为 DP 数组，因此不需要额外的空间。

Author：liangweijiang

原文链接：https://liangweijiang.github.io/2020/04/01/algorithm-62-63/

发表日期：April 1st 2020, 4:05:08 pm

更新日期：April 7th 2020, 3:27:10 pm

Next Post

数据结构学习笔记---散列表
Previous Post

每日一道算法之--跳跃游戏

CATALOG

1. 不同路径
1. 1.1. 动态规划
  1. 1.1.1. 复杂度分析
2. 1.2. 优化动态规划
2. 不同路径II
1. 2.1. 动态规划

