今天开始逐渐有 dp的感觉了，前 两题 不同路径，可以好好研究一下，适合进阶
详细布置
62.不同路径
本题大家掌握动态规划的方法就可以。 数论方法 有点非主流，很难想到。
https://programmercarl.com/0062.不同路径.html
视频讲解：https://www.bilibili.com/video/BV1ve4y1x7Eu
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
var uniquePaths = function(m, n) {
const dp = new Array(m).fill(1).map(()=>new Array(n).fill(1));
// for (let i=0;i<n;i++) {
// dp[0][i] = 1;
// }
// for (let i=0;i<m;i++) {
// dp[i][0] = 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];
};
- 不同路径 II
https://programmercarl.com/0063.不同路径II.html
视频讲解：https://www.bilibili.com/video/BV1Ld4y1k7c6
这题要注意初始化的时候，如果障碍物在第一行或第一列，，障碍物后面的值都为0
/**
* @param {number[][]} obstacleGrid
* @return {number}
*/
var uniquePathsWithObstacles = function(obstacleGrid) {
if (obstacleGrid[0][0] === 1) return 0;
let m = obstacleGrid.length;
let n = obstacleGrid[0].length;
const dp = new Array(m).fill(0).map(()=>new Array(n).fill(0));
for(let i=0;i<m;i++) {
if (obstacleGrid[i][0]===1) {
dp[i][0] = 0;
break;
} else {
dp[i][0] = 1;
}
}
for(let i=0;i<n;i++) {
if (obstacleGrid[0][i]===1) {
dp[0][i] = 0;
break;
} else {
dp[0][i] = 1;
}
}
for (let i=1;i<m;i++) {
for(let j =1;j<n;j++) {
if (obstacleGrid[i][j]===1) {
dp[i][j] = 0;
} else {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
return dp[m-1][n-1];
};
- 整数拆分 （可跳过）
本题思路并不容易想，一刷建议可以跳过。如果学有余力，可以看视频理解一波。
https://programmercarl.com/0343.整数拆分.html
视频讲解：https://www.bilibili.com/video/BV1Mg411q7YJ
96..不同的二叉搜索树 （可跳过）
本题思路并不容易想，一刷建议可以跳过。 如果学有余力，可以看视频理解一波。
https://programmercarl.com/0096.不同的二叉搜索树.html
视频讲解：https://www.bilibili.com/video/BV1eK411o7QA