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。

该题考察的知识点是动态规划

1. 创建二维数组dp，用于记录从起点到每个位置的路径数量。
2. 初始化起点，如果起点没有障碍物，则路径数量为1，否则为0。
3. 初始化第一列的路径数量，如果当前位置没有障碍物，则路径数量等于上方位置的路径数量。
4. 初始化第一行的路径数量，如果当前位置没有障碍物，则路径数量等于左方位置的路径数量。
5. 填充dp数组，计算从起点到每个位置的路径数量。如果当前位置没有障碍物，则路径数量等于从上方和左方到达当前位置的路径数量之和。
6. 返回从左上角到右下角的路径数量，即dp数组的最后一个元素。