题意：

image.png

解题思路：

  1. 思路：动态规划
  2. 状态：dp[i][j] 表示走到格子(i,j) 的方法数。
  3. 状态转移方程：
  4.     1.1 如果网格 (i,j)上有障碍物，则 dp[i][j]值为 0，表示走到该格子的方法数为0；
  5.     1.2 否则网格 (i,j)可以从网格(i−1,j) 或者 网格(i,j−1) 走过来，
  6.     因此走到该格子的方法数为走到网格(i−1,j)和网格(i,j−1) 的方法数之和，
  7.     即 dp[i,j]=dp[i−1,j]+dp[i,j−1]。

PHP代码实现：

  1. class Solution {
  3.     /**
  4.      * @param Integer[][] $obstacleGrid
  5.      * @return Integer
  6.      */
  7.     function uniquePathsWithObstacles($grid) {
  8.         $row = count($grid);//行
  9.         $col = count($grid[0]);//列
  10.         //初始有障碍物直接返回0
  11.         $grid[0][0] = $grid[0][0] == 1 ? 0 : 1;
  13.         // 如果当前的位置为0，表示当前没有障碍。并且前一步为1，表示前一步没有障碍，走过了就变为1
  14.         // 那么这一步就可以变为1，否则就是有障碍，置为0
  15.         for ($i = 1; $i < $row; $i++) 
  16.             $grid[$i][0] = ($grid[$i][0] == 0 && $grid[$i - 1][0] == 1) ? 1 : 0; //先处理行
  18.         for ($i = 1; $i < $col; $i++)
  19.             $grid[0][$i] = ($grid[0][$i] == 0 && $grid[0][$i - 1] == 1) ? 1 : 0; 
  21.         for ($i = 1; $i < $row; $i++) {
  22.             for ($j = 1; $j < $col; $j++) {
  23.                 if ($grid[$i][$j] == 0) {
  24.                     $grid[$i][$j] = $grid[$i-1][$j] + $grid[$i][$j-1];   
  25.                 } else {
  26.                     $grid[$i][$j] = 0;
  27.                 }
  28.             }
  29.         }
  30.         return $grid[$row-1][$col-1];    
  31.     }
  32. }

GO代码实现：

  1. func uniquePathsWithObstacles(grid [][]int) int {
  2.     dp := make([][]int, len(grid))
  3.     for i := 0;i < len(grid);i++ {
  4.         dp[i] = make([]int, len(grid[0]))
  5.     }
  6.     for i := 0;i < len(grid);i++ {
  7.         if grid[i][0] == 1 {
  8.             dp[i][0] = 0
  9.             break
  10.         }
  11.         dp[i][0] = 1
  12.     }
  13.     for i := 0;i < len(grid[0]);i++ {
  14.         if grid[0][i] == 1 {
  15.             dp[0][i] = 0
  16.             break
  17.         }
  18.         dp[0][i] = 1
  19.     }
  20.     for i := 1;i < len(grid);i++ {
  21.         for j := 1;j < len(grid[0]);j++ {
  22.             if grid[i][j] == 1 {
  23.                 dp[i][j] = 0
  24.                 continue
  25.             }
  26.             dp[i][j] = dp[i][j-1] + dp[i-1][j]
  27.         }
  28.     }
  29.     return dp[len(dp)-1][len(dp[0])-1]
  30. }