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];
}

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