不同路径
力扣题目链接
简单分析其实不难。
- dp含义：从（0 ，0）出发，到第i，j位置有几条路径
- 除了第一列和第一行的元素，只有一条路径。
其他行列的元素的路径，为左边元素路径及上边元素路径之和。
再根据动规五部曲进行详细分析。
var uniquePaths = function(m, n) {
let dp = new Array(m).fill(0).map(() => {
return new Array(n).fill(0);
});
for (let i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (let j = 0; j < n; j++) {
dp[0][j] = 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];
};
改进：
可直接将dp数组初始化为1
不同路径2
力扣题目链接
与上题的区别：
- 初始化需要修改。第一行或第一列遇到第一个障碍物，后续均初始化为0
- 递推公式。分情况讨论。有障碍物时，dp[i][j]为0；否则为左边元素路径及上边元素路径之和。
再根据动规五部曲进行详细分析。
var uniquePathsWithObstacles = function(obstacleGrid) {
const m = obstacleGrid.length;
const n = obstacleGrid[0].length;
let dp = new Array(m).fill(0).map(() => {
return new Array(n).fill(1);
});
// 初始化
for (let i = 0; i < m; i++) {
if (obstacleGrid[i][0] > 0) {
//遇到第一个障碍物，后面的均初始化为0
while (i < m) {
dp[i][0] = 0;
i++;
}
break;
}
}
for (let j = 0; j < n; j++) {
if (obstacleGrid[0][j] > 0) {
while (j < n) {
dp[0][j] = 0;
j++;
}
break;
}
}
// 求值
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
// 有障碍物
if (obstacleGrid[i][j] > 0) {
dp[i][j] = 0;
} else {//无障碍物
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[m - 1][n - 1];
};
