Leetcode63_DP走方格

题目：https://leetcode-cn.com/problems/unique-paths-ii/

状态定义

$dp[i][j]$ 表示走到格子 $(i,j)$ 的路径数

状态计算

如果网格 $(i,j)$ 上有障碍物，则 $dp[i][j]$ 值为0，走到这个格子的方法数为0

否则网格 $(i,j)$ 可以从网格 $(i-1,j)$ 或者网格 $(i,j-1)$ 走过来，因此走到该格子的方法数为走到网格 $
(i-1,j)$ 和网格$(i,j-1)$ 的方法数之和，即: $dp[i,j] = dp[i-1,j] + dp[i,j-1]$

初始条件

第 1 列的格子只有从其上边格子走过去这一种走法，因此初始化 $dp[i][0]$ 值为 1，存在障碍物时为 0；

第一行的格子只有从其左边格子走过去这一种走法，因此初始化$dp[0][j]$ 值为1，存在障碍物事为0；

1
2
3
4
5
6
7
8
int[][] dp = new int[m][n];
for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
    dp[i][0] = 1;
}
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
    dp[0][j] = 1;
}

具体实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int uniquePathWithObstacles(int[][] grid){
  	if (obstacleGrid == null || obstacleGrid.length == 0) {
       return 0;
    }
		int m=grid.length;
  	int n=grid[0].length;
  	
  	int[][] dp=new int[m][n];
  	for(int i=0;i<m && grid==0;i++){
       dp[i][0] = 1;
    }
  	for(int i=0;i<n && grid==0;i++){
      	dp[0][j] = 1;
    }
  
  	for(int i=1;i<m;i++){
      	for(int j=1;j<n;j++){
          if(grid[i][j]==0){
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
          }
        }
    }
  return dp[m-1][n-1];
}

同理没有障碍物就删掉判断条件。