//1.  状态定义： f[i][j] 表示到达i,j这个点的独立路径个数
//2.  状态计算： f[i][j] = f[i-1][j] + f[i][j-1]  的非障碍点
//3.  边界： f[~][~] = 0, f[1][1] = 1
// 还要考虑 起点|| 终点也是障碍的情况
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid[0] == null) return 0;
        int n = obstacleGrid.length;
        int m = obstacleGrid[0].length;

        int[][] f = new int[n+2][m+2];
        f[1][1] = obstacleGrid[0][0] == 0 ? 1 : 0;
        for (int i = 1 ; i <= n ; i ++){
            for(int j = 1 ; j <= m ; j++){
                if (obstacleGrid[i-1][j-1] == 1) continue;
                if (i >= 2 && obstacleGrid[i-2][j-1] == 0) f[i][j] += f[i-1][j];
                if (j >= 2 && obstacleGrid[i-1][j-2] == 0) f[i][j] += f[i][j-1];
            }
        }
        return f[n][m];
    }
}