原題鏈接：https://leetcode-cn.com/problems/unique-paths-ii/
解題思路：
- 在網(wǎng)格中的任意一點(diǎn)女坑，都有向右和向下兩種路徑。同時(shí)它也是從上方和左方兩個(gè)位置走過來的统舀。
- 那么匆骗，任意一點(diǎn)的路徑數(shù)量劳景，等于從起點(diǎn)走到上方和左方點(diǎn)的數(shù)量之和。
- 第一行和第一列都只有一種路徑碉就，就是從起點(diǎn)一直走到底枢泰。
- 我們可以用一個(gè)二維數(shù)組，畫出網(wǎng)格中每個(gè)點(diǎn)的路徑數(shù)量铝噩，一直遞推到終點(diǎn)衡蚂，終點(diǎn)存儲的就是所有的路徑數(shù)量。
- 因此動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程為：
dp[i][j]=dp[i-1][j]+dp[i][j-1]骏庸。 - 如果遇到障礙物毛甲，則該位置的路徑數(shù)量為0。
- 對于起始點(diǎn)
obstacleGrid[0][0]具被，如果它沒有障礙物玻募，路徑為1，反之為0一姿。 - 由于每個(gè)點(diǎn)的路徑數(shù)量只和它左方和上方有關(guān)七咧，因此狀態(tài)轉(zhuǎn)移方程可以優(yōu)化為：
dp[i] = dp[i - 1] + dp[i]。
/**
* @param {number[][]} obstacleGrid
* @return {number}
*/
var uniquePathsWithObstacles = function(obstacleGrid) {
// 創(chuàng)建數(shù)組叮叹，存儲最新一行的狀態(tài)
// 由于新位置的狀態(tài)艾栋，只與它左方和上方的狀態(tài)有關(guān)
// 也就是dp[j] = dp[j - 1] + dp[j]
// 因此只需要一維數(shù)組即可
let dp = new Array(obstacleGrid[0].length).fill(0)
// 起始位置如果無障礙物，路徑為1蛉顽，否則為0
dp[0] = obstacleGrid[0][0] ? 0 : 1
// 遍歷每個(gè)網(wǎng)格位置蝗砾，計(jì)算路徑數(shù)量
for (let i = 0; i < obstacleGrid.length; i++) {
for (let j = 0; j < obstacleGrid[0].length; j++) {
// 如果遇到障礙物，當(dāng)前位置無法經(jīng)過携冤，路徑為0
if (obstacleGrid[i][j]) {
dp[j] = 0
} else {
// 如果當(dāng)前位置沒有障礙物悼粮，路徑數(shù)量等于左方和上方的數(shù)量之和
// 如果j為0，dp[j - 1]為undefined曾棕，將其設(shè)置為0扣猫，方便計(jì)算
dp[j] += dp[j - 1] ?? 0
}
}
}
// 最后一個(gè)位置存儲的就是最終結(jié)果
return dp[obstacleGrid[0].length - 1]
};
