题解 | #挤奶路径# java

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; // 获取农场的列数

        // 创建二维数组dp，用于记录从起点到每个位置的路径数量
        int[][] dp = new int[m][n];

        // 初始化起点，如果起点没有障碍物，则路径数量为1，否则为0
        dp[0][0] = (cows[0][0] == 0) ? 1 : 0;

        // 初始化第一列的路径数量
        for (int i = 1; i < m; i++) {
            if (cows[i][0] == 0) {
                dp[i][0] = dp[i - 1][0];
            }
        }

        // 初始化第一行的路径数量
        for (int j = 1; j < n; j++) {
            if (cows[0][j] == 0) {
                dp[0][j] = dp[0][j - 1];
            }
        }

        // 填充dp数组，计算从起点到每个位置的路径数量
        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];
                }
            }
        }

        // 返回从左上角到右下角的路径数量，即dp数组的最后一个元素
        return dp[m - 1][n - 1];
    }
}

编程语言是Java。

该题考察的知识点包括：

• 动态规划：通过构建一个二维数组来保存中间状态，以解决更大规模的问题。在这个问题中，使用动态规划来计算从左上角到右下角的路径数量，考虑了可能的障碍物。
• 数组操作：创建二维数组，根据条件填充数组元素。

文字解释：这创建一个与输入矩阵相同大小的二维数组，逐步计算每个位置的路径数量。初始化起点和第一行、第一列的路径数量，然后根据当前位置的情况，计算从上方和左方到达当前位置的路径数量之和。最终，返回右下角位置的路径数量作为结果。