题解 | #挤奶路径#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cows int整型二维数组 
     * @return int整型
     */
    public int uniquePathsWithObstacles(int[][] cows) {
        int[][] dp = new int[cows.length][cows[0].length];
        // 初始化dp数组
        for (int i = 0; i < cows.length; i++) {
            if (cows[i][0] == 0) {
                dp[i][0] = 1;
            }else{
                break;
            }
        }
        for (int i = 0; i < cows[0].length; i++) {
            if (cows[0][i] == 0) {
                dp[0][i] = 1;
            } else{
                break;
            }
        }
        for (int i = 1; i < cows.length; i++) {
            for (int j = 1; j < cows[0].length; j++) {
                if(cows[i][j]==1){
                    dp[i][j] = 0;
                }else{
                    dp[i][j] = dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[cows.length-1][cows[0].length-1];
    }
}

本题知识点分析：

1.动态规划

2.数组遍历

3.数学模拟

本题解题思路分析：

1.dp数组是什么？dp数组代表到底m,n位置有几种解法

2.dp数组推导公式， dp[i][j] = dp[i-1][j]+dp[i][j-1];常规公式，要么是向右走到的，要么是向下走到的。

3.dp数组初始化，初始化第一行和第一列就行，如果遇到0说明可以走，那么dp设置为1，有一种解法，如果遇到了1直接break,因为后面的格子必不可能走，因为不能返回走，比如向上或者向左是不可能的。注意break。

4.确定遍历顺序，从dp[1][1]开始，如果遇到了障碍物，那么设置为0，否则解法就是 dp[i][j] = dp[i-1][j]+dp[i][j-1];也就是求和。

本题使用编程语言: Java

如果您觉得本篇文章对您有帮助，可以点个赞支持一下，感谢~