题解 | #不同路径的数目(二)#
不同路径的数目(二)
https://www.nowcoder.com/practice/2bbfd075fbde4884b9da80634e1cae7c
动态规划问题,与没有障碍物的区别在于,初始化时第一行第一列遇到障碍物时,此处以及后面的dp都为0.且递推时,遇到障碍物dp为0,其他仍然按照dp[i][j]=dp[i-1][j]+dp[i][j-1]的递推关系进行。
function uniquePathsWithObstacles( obstacleGrid ) { // write code here const m = obstacleGrid.length, n = obstacleGrid[0].length; let dp = Array(m).fill().map(item => Array(n).fill(0)); for(let i = 0; i < m; i ++){ if(obstacleGrid[i][0]){ dp[i][0] = 1; } else { break; } } for(let i = 0; i < n; i ++){ if(obstacleGrid[0][i]){ dp[0][i] = 1; } else { break; } } for(let i = 1; i < m; i ++){ for(let j = 1; j < n; j ++){ if(obstacleGrid[i][j]){ dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } else { dp[i][j] = 0; } } } return dp[m - 1][n - 1]; } module.exports = { uniquePathsWithObstacles : uniquePathsWithObstacles };