题解 | #挤奶路径2#

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

1. 将矩阵分为两部分，一部分是从左上角到奶牛所在位置的路径，另一部分是从奶牛所在位置到右下角的路径
2. 定义一个二维数组 dp，其中 dp[i][j] 表示从起点到 (i,j) 的路径数量。
3. 初始化 dp[start_i][start_j] 为 1，表示起点只有一条到达自己的路径。
4. 遍历矩阵中的所有位置，对于每个位置 (i, j)，如果不是起点，则：如果这个位置是障碍物，则将 dp[i][j] 设为 0，表示无法到达这个位置；否则，dp[i][j] 可以从上方或左侧到达，因此 dp[i][j] = dp[i-1][j] + dp[i][j-1]。
5. 最后返回 dp[end_i][end_j]，其中 end_i 和 end_j 分别为终点的行和列。

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

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

    def uniquePaths(
        self, cows: List[List[int]], start_i: int, start_j: int, end_i: int, end_j: int
    ) -> int:
        m, n = len(cows), len(cows[0])
        dp = [[0] * n for _ in range(m)]
        dp[start_i][start_j] = 1
        for i in range(start_i, end_i + 1):
            for j in range(start_j, end_j + 1):
                if i != start_i or j != start_j:
                    if cows[i][j] != 1:
                        dp[i][j] = (dp[i - 1][j] if i > 0 else 0) + (
                            dp[i][j - 1] if j > 0 else 0
                        )
        return dp[end_i][end_j]