题解 | #挤奶路径#

一、知识点：

动态规划

二、文字分析：

这个问题可以使用动态规划来解决。我们可以创建一个与农场大小相同的二维数组dp，dp[i][j]表示从起点到达位置(i, j)的不同路径数目。

1. 如果农场的起点位置有障碍物，直接返回0，因为无法到达终点。
2. 初始化dp[0][0]为1，表示起点位置的路径数。
3. 初始化第一列，如果有障碍物或者前一个位置路径数为0，则从当前位置开始后面的路径不可达，将dp[i][0]置为0。
4. 初始化第一行，如果有障碍物或者前一个位置路径数为0，则从当前位置开始后面的路径不可达，将dp[0][j]置为0。
5. 对于其他位置(i, j)，如果当前位置有障碍物，则将dp[i][j]置为0；否则，将当前位置的路径数等于左边位置的路径数加上上面位置的路径数，即dp[i][j] = dp[i-1][j] + dp[i][j-1]。
6. 返回dp[m-1][n-1]，即从起点到终点的不同路径数目。

• 时间复杂度：假设农场的大小为m x n。初始化dp数组需要遍历整个农场，所以时间复杂度为O(m x n)。对于每个位置(i, j)，计算dp[i][j]的路径数需要参考左边位置和上边位置的路径数，所以总共需要遍历农场中的每个位置，时间复杂度为O(m x n)。因此，整体时间复杂度为O(m x n)。
• 空间复杂度：除了输入的农场二维数组外，我们使用了一个与农场大小相同的二维数组dp来保存路径数，所以空间复杂度为O(m x n)。

三、编程语言：

java

四、正确代码：

import java.util.*;


public class Solution {
    public int uniquePathsWithObstacles(int[][] cows) {
        int m = cows.length;
        int n = cows[0].length;

        // 如果起点有障碍物，直接返回0
        if (cows[0][0] == 1) {
            return 0;
        }

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

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

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

        // 计算其他位置的路径数
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (cows[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }

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