题解 | #挤奶路径#

考察的知识点：动态规划；

解答方法分析：

1. 定义一个二维数组dp，其中dp[i][j]表示从起点到达位置(i, j)的不同路径数目。
2. 初始化dp数组。由于只能向下或向右移动，所以第一行和第一列的位置只能从左方或上方到达，因此，如果某个位置有障碍物或者其左方或上方有障碍物，则该位置的路径数为0，否则为1。
3. 使用动态规划的思想来递推整个dp数组。对于位置(i, j)，从左方和上方到达，到达位置(i, j)的路径数等于到达其左方位置(i-1, j)的路径数加上到达其上方位置(i, j-1)的路径数，即dp[i][j] = dp[i-1][j] + dp[i][j-1]。但是如果位置(i, j)有障碍物，则路径数为0，即dp[i][j] = 0。
4. 返回结果dp[m-1][n-1]。

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    int uniquePathsWithObstacles(vector<vector<int> >& cows) {
        int m = cows.size();
        int n = cows[0].size();
        vector<vector<int> > dp(m, vector<int>(n));
        for (int i = 0; i < m; i++) {
            if (cows[i][0] == 1) {
                break;
            }
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            if (cows[0][j] == 1) {
                break;
            }
            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];
    }
};