题解 | #挤奶路径#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param cows int整型二维数组
     * @return int整型
     */
    public int uniquePathsWithObstacles (int[][] cows) {
        // write code here
        int m = cows.length;
        int n = cows[0].length;

        int[][] dp = new int[m][n];

        // Initialize the first row and first column
        for (int i = 0; i < m && cows[i][0] == 0; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n && cows[0][j] == 0; j++) {
            dp[0][j] = 1;
        }

        // Fill in the DP array using bottom-up approach
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (cows[i][j] == 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }

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

知识点：

1. 动态规划：一种通过将问题分解成子问题，并存储子问题的解来解决问题的方法。
2. 二维网格：一个由行和列组成的矩阵结构，通常用来表示图形、地图等。

解题思路：

使用了一个二维动态规划数组 dp 来存储从起点到每个位置的不同路径数量。我们通过初始化第一行和第一列的路径数量，然后根据障碍物情况迭代填充 dp 数组。最终，我们返回 dp[m-1][n-1]，其中 m 和 n 分别是二维网格的行数和列数。