### 主要收获

#### 练习写自底向上的动态规划

自顶向下的带备忘录的动态规划虽然通过查表避免了重复计算子问题，但并没有避免子问题被提出。子问题的数量还是指数级的，方法的调用也是指数级的。

自底向上的动态规划，每个子问题都只被提出一次，并计算一次。所以是多项式复杂度

### 题目

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example, There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
[0,0,0],
[0,1,0],
[0,0,0]
]


The total number of unique paths is 2.

Note: m and n will be at most 100.

### 带备忘录的动态规划 指数级复杂度

#### 代码

public class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int lineSize = obstacleGrid.length;
if (lineSize == 0) { return 0; }
int columnSize = obstacleGrid[0].length;
if (columnSize == 0) { return 0; }
int[][] memo = new int[lineSize][columnSize];
return dp(obstacleGrid,memo,lineSize-1,columnSize-1,0,0);
}
public int dp(int[][] obs, int[][] memo, int lineSize, int columnSize, int m, int n) {
if (obs[m][n] == 1) { return 0; }
if (m == lineSize && n == columnSize) { return 1; }
if (memo[m][n] != 0) { return memo[m][n]; }
int rightCount = 0, downCount = 0;
if (m < lineSize) { rightCount = dp(obs,memo,lineSize,columnSize,m+1,n); }
if (n < columnSize) { downCount = dp(obs,memo,lineSize,columnSize,m,n+1); }
int res = rightCount + downCount;
memo[m][n] = res;
return res;
}
}


#### 结果

Visual VM检查了一下，发现103秒中有81秒花在了1704611784次（17亿次）对dp()方法的调用。

### 自底向上的动态规划 $O(mn)$

#### 代码

public class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int lineSize = obstacleGrid.length;
if (lineSize == 0) { return 0; }
int columnSize = obstacleGrid[0].length;
if (columnSize == 0) { return 0; }
int[][] memo = new int[lineSize][columnSize];
for (int i = lineSize-1; i >= 0; i--) {
for (int j = columnSize-1; j >= 0; j--) {
if (obstacleGrid[i][j] == 1) { memo[i][j] = 0; continue; }
if ( (i == lineSize-1) && (j == columnSize-1) ) { memo[i][j] = 1; continue; }
if (i == lineSize-1) { memo[i][j] = memo[i][j+1]; continue; }
if (j == columnSize-1) { memo[i][j] = memo[i+1][j]; continue; }
memo[i][j] = memo[i+1][j] + memo[i][j+1];
}
}
return memo[0][0];
}
}