题解 | #挤奶路径#

知识点

动态规划

解题思路

定义一个二维数组dp，dp[i][j]表示从农场的左上角到达位置(i, j)的不同路径数。

首先，我们初始化dp数组。如果农场的左上角有障碍物（即cows[0][0]为1），则路径数为0；否则，路径数为1，即dp[0][0] = 1。

然后，我们根据动态规划的递推关系式来更新dp数组。对于位置(i, j)，如果当前位置为障碍物，则路径数为0，即dp[i][j] = 0。否则，可以根据上方位置和左方位置的路径数来计算当前位置的路径数，即dp[i][j] = dp[i-1][j] + dp[i][j-1]。

最后的dp[m-1][n-1]就是最终ans。

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;

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

        // 初始化第一个位置
        if (cows[0][0] == 0) {
            dp[0][0] = 1;
        } else {
            dp[0][0] = 0;
        }

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

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

        // 更新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];
                } else {
                    dp[i][j] = 0;
                }
            }
        }

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