leetcode-63-不同陆路径II

题解：

1、设dp[i][j]为到达(i,j)点的路径。当grid[i][j]==1时,dp[i][j]==0;否则dp[i][j]为到达(i-1,j)的最多路径与到达(i,j-1)的最多路径之和。当(i,j)位于第一行时，dp[i][j]=dp[i][j-1]。当(i,j)位于第一列时，dp[i][j]=dp[i-1][j]。

2、初始化M*N的元素为0的数组dp[i][j]。设置dp[0][0]=1。

3、遍历数组obstacleGrid。如果obstacleGrid[i][j]==1，dp[i][j]=0。否则，当(i,j)位于第一行时，dp[i][j]=dp[i][j-1]；当(i,j)位于第一列时，dp[i][j]=dp[i-1][j]；当(i,j)在其他位置时,dp[i][j]=dp[i-1][j]+dp[i][j-1]。

4、返回dp[-1][-1]

代码：