题解 | #挤奶路径#

题目考察的知识点

多维动态规划，路径转移数

题目解答方法的文字分析

我们假设dp[i][j]代表走到第i行第j列的方法数，显然，为了走到第（i，j）位：

①：当(i,j)不是障碍时需要从第（i-1，j）或（i，j-1）走过来，那么可以得到动态规划的转移方程：

dp[i][j]=dp[i-1][j]+dp[i][j-1];

②当（i，j）是障碍时，dp[i][j]=0(显然走不到) 此外，还需要注意第0行和第0列的初始化，它们都只能从（0,0）开始走，在出现障碍前的路径方法数皆为1.一旦出现障碍，那么后面的位置都走不到了，方法数为0。

本题解析所用的编程语言

c++

完整且正确的编程代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cows int整型vector<vector<>> 
     * @return int整型
     */
    int uniquePathsWithObstacles(vector<vector<int> >& cows) {
        int dp[55][55];
        int m=cows.size();
        int n=cows[1].size();
      for(int i=0;i<m;i++)//初始化第一列
      {
        if(cows[i][0]==0)dp[i][0]=1;
         else break;
      }
      for(int i=0;i<n;i++)//初始化第一行
      {
        if(cows[0][i]==0)dp[0][i]=1;
        else break;
      }
        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];
    }
};