[Leetcode][python]Unique Paths/Unique Paths II

左手的ㄟ右手 2022-06-07 07:13 400阅读 0赞

# Unique Paths #

## 题目大意 ##

机器人从起点到终点有多少条不同的路径，只能向右或者向下走。

## 解题思路 ##

动态规划  
由于只能有向下向右，只有从\[1\]\[1\]开始的格子需要选择走法，第一行和第一列所有都只有一种走法，所有都设置成1，（这里图方便所有都初始化为1），然后循环计算出所有其他的。

dp[j][i] = dp[j - 1][i] + dp[j][i - 1]

## 代码 ##

class Solution(object):
        def uniquePaths(self, m, n):
            """
            :type m: int
            :type n: int
            :rtype: int
            """
            dp = [[1 for __ in range(n)] for __ in range(m)]
            # print dp
            for i in range(1, n):
                for j in range(1, m):
                    dp[j][i] = dp[j - 1][i] + dp[j][i - 1]
            return dp[m - 1][n - 1]

# Unique Paths II #

## 题目大意 ##

如果道路上有障碍，机器人从起点到终点有多少条不同的路径，只能向右或者向下走。0表示道路通行，1表示有障碍。

## 解题思路 ##

和上题区别仅仅是有障碍，那么有障碍的地方就是0（不可能走到），然后初始化一下第一行和第一列（**若其中有障碍则之后皆为0**），最后还是上题那样做。

dp[j][i] = dp[j - 1][i] + dp[j][i - 1] (s[i][j] != 1) # 无障碍
    dp[j][i] = 0 (s[i][j] = 1) # 有障碍

## 代码 ##

class Solution(object):
        def uniquePathsWithObstacles(self, obstacleGrid):
            """
            :type obstacleGrid: List[List[int]]
            :rtype: int
            """
            if obstacleGrid[0][0] == 1:  # 如果第一个格子有障碍，就无法走
                return 0
            m = len(obstacleGrid)  # 纵向
            n = len(obstacleGrid[0])  # 横向
            dp = [[0 for __ in range(n)] for __ in range(m)]  # 初始化，所有为0
            # 第一个可以走设置为1
            dp[0][0] = 1
            # 检查第一行和第一列是否有障碍
            for i in range(1, m):
                dp[i][0] = dp[i - 1][0] if obstacleGrid[i][0] == 0 else 0
            for j in range(1, n):
                dp[0][j] = dp[0][j - 1] if obstacleGrid[0][j] == 0 else 0
    
            for i in range(1, m):
                for j in range(1, n):
                    if obstacleGrid[i][j] == 1:
                        dp[i][j] = 0
                    else:
                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
            return dp[m - 1][n - 1]

## 总结 ##