63. Unique Paths II

// obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
// 输出: 2

// dp[i][j] 表示从起点 (0, 0) 到 (i-1, j-1) 的不同路径数。
// 状态方程：如果当前格子是障碍物（obstacleGrid[i-1][j-1] === 1），则 dp[i][j] = 0。否则，dp[i][j] = dp[i-1][j] + dp[i][j-1]，即从上方或左方到达当前格子的路径数之和。
// 初始化：dp[1][1] = 1，表示起点到起点的路径数为 1（前提是起点不是障碍物）。其他 dp[i][j] 初始化为 0。


/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function(obstacleGrid) {
    m=obstacleGrid.length;
    n=obstacleGrid[0].length;

    let dp = Array.from({length: m+1}, () => Array(n+1).fill(0));

    if (obstacleGrid[0][0] === 0) {
        dp[1][1] = 1;
    }
    

    for(let i=1;i<=m;i++){
        for(let j=1;j<=n;j++){
            if(i===1 && j===1){
                continue;
            }
            if(obstacleGrid[i-1][j-1]===0){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
    }

    return dp[m][n];
};