代码随想录第39天 | 62. 不同路径、63.不同路径II

62. 不同路径

动态规划五部曲：

1. dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
2. 想要求dp[i][j]，只能有两个方向来推导出来，即dp[i - 1][j] 和 dp[i][j - 1]。dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。
3. 首先dp[i][0]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp[0][j]也同理。
4. 从左到右一层一层遍历就可以了。这样就可以保证推导dp[i][j]的时候，dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的。
5. 验证dp数组

/*** @param {number} m* @param {number} n* @return {number}*/
var uniquePaths = function (m, n) {let dp = new Array(m).fill().map(() => new Array(n))for (let i = 0; i < m; ++i) {dp[i][0] = 1}for (let i = 0; i < n; ++i) {dp[0][i] = 1}for (let i = 1; i < m; i++) {for (let j = 1; j < n; j++) {dp[i][j] = dp[i - 1][j] + dp[i][j - 1]}}return dp[m - 1][n - 1]
};

63.不同路径II

比前一题多了障碍的限制条件。

五部曲：

1. dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
2. 递推公式和62.不同路径一样，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。因为有了障碍，(i, j)如果就是障碍的话应该就保持初始状态（初始状态为0）。
3. 如果(i, 0) 这条边有了障碍之后，障碍之后（包括障碍）都是走不到的位置了，所以障碍之后的dp[i][0]应该还是初始值0。
4. 从左到右一层一层遍历，这样保证推导dp[i][j]的时候，dp[i - 1][j] 和 dp[i][j - 1]一定是有数值。
5. 举例推导dp

/*** @param {number[][]} obstacleGrid* @return {number}*/
var uniquePathsWithObstacles = function (obstacleGrid) {let m = obstacleGrid.lengthlet n = obstacleGrid[0].lengthlet dp = new Array(m).fill().map(() => new Array(n).fill(0))for (let i = 0; i < m; i++) {if (obstacleGrid[i][0]) breakdp[i][0] = 1}for (let i = 0; i < n; i++) {if (obstacleGrid[0][i]) breakdp[0][i] = 1}for (let i = 1; i < m; i++) {for (let j = 1; j < n; j++) {dp[i][j] = obstacleGrid[i][j] === 1 ? 0 : dp[i - 1][j] + dp[i][j - 1]}}return dp[m - 1][n - 1]
};