题解 | #挤奶路径#

• 题目考察的知识点 : 动态规划
• 题目解答方法的文字分析：

1. 用一个二维 DP 数组 dp 来记录从起点到达每个位置的路径数
2. 需要初始化 dp[0][0] 为 1，表示从起点出发只有一种走法。对于第一行和第一列的位置（即 i=0 或 j=0），由于它们只能向下或向右移动，因此也都只有一种走法，应该将其初始化为 1。
3. 起点到达位置 (i, j) 的路径数等于从上方 (i-1, j) 和左侧 (i, j-1) 到达该位置的路径数之和。需要注意的是，在计算 dp[i][j]时，应该先判断当前位置是否是障碍物。最后，dp[m-1][n-1] 就是从起点到达右下角的路径总数

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param cows int整型二维数组
# @return int整型
#
class Solution:
    def uniquePathsWithObstacles(self, cows: List[List[int]]) -> int:
        m, n = len(cows), len(cows[0])
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = 1 if cows[0][0] == 0 else 0

        # 初始化第一行和第一列
        for i in range(1, m):
            dp[i][0] = dp[i - 1][0] if cows[i][0] == 0 else 0
        for j in range(1, n):
            dp[0][j] = dp[0][j - 1] if cows[0][j] == 0 else 0

        # 动态规划
        for i in range(1, m):
            for j in range(1, n):
                if cows[i][j] == 0:
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

        return dp[m - 1][n - 1]