题目:
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用 1 和 0 来表示。
m 和 n 的值均不超过 100。
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径:
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
先计算没有障碍物时从一个位置到另外一个位置的方式思路
实现
var uniquePaths = function (obstacleGrid) {
let m = obstacleGrid.length,
n = obstacleGrid[0] ? obstacleGrid[0].length : 0,
cur = Array(m).fill(Array(n).fill(1))
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
cur[i][j] += cur[i][j - 1]
}
}
return cur[m - 1][n - 1]
}
观察上面的逻辑会发下,迭代时涉及计算都是在单行中进行及 i 不变 那么尝试对矩阵降维,只记录结束值到这一列看下,优化:
var uniquePaths = function (obstacleGrid) {
let m = obstacleGrid.length,
n = obstacleGrid[0] ? obstacleGrid[0].length : 0,
cur = Array(n).fill(1)
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
cur[j] += cur[j - 1]
}
}
return cur[n - 1]
}
回到本题,如果遇到障碍:
/**
* @param {number[][]} obstacleGrid
* @return {number}
*/
var uniquePathsWithObstacles = function (obstacleGrid) {
let m = obstacleGrid.length,
n = obstacleGrid[0] ? obstacleGrid[0].length : 0,
cur = Array(m).fill(0)
cur[0] = obstacleGrid[0][0] == 0 ? 1 : 0
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
// 遇到障碍
if (obstacleGrid[i][j] === 1) {
cur[j] = 0
} else if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
cur[j] += cur[j - 1]
}
}
}
return cur[n - 1]
}
如果上面只记录目的地是列的逻辑不易理解的话,再升维,来个直观的方式:
cur[i][j]记录从 cur[0][0]到其的所有方式
/**
* @param {number[][]} obstacleGrid
* @return {number}
*/
var uniquePathsWithObstacles = function (obstacleGrid) {
let m = obstacleGrid.length,
n = obstacleGrid[0] ? obstacleGrid[0].length : 0,
cur = Array(m).fill(Array(n).fill(0))
// 起点不能为障碍
cur[0][0] = obstacleGrid[0][0] == 0 ? 1 : 0
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
// 遇到障碍
if (obstacleGrid[i][j] === 1) {
cur[i][j] = 0
} else if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
// 上一步不是障碍
cur[i][j] += cur[i][j - 1]
}
}
}
return cur[m - 1][n - 1]
}
注意:
原题解(可点击阅读原文查找链接)
/**
* @param {number[][]} obstacleGrid
* @return {number}
*/
var uniquePathsWithObstacles = function (obstacleGrid) {
if (obstacleGrid[0][0] == 1) return 0
let m = obstacleGrid.length,
n = obstacleGrid[0] ? obstacleGrid[0].length : 0,
cur = Array(m)
for (let i = 0; i < m; i++) cur[i] = Array(n)
// 初始化起点
cur[0][0] = 1
for (let i = 1; i < m; i++) {
// 初始化基准列:第一列
cur[i][0] = obstacleGrid[i][0] == 1 || cur[i - 1][0] == 0 ? 0 : 1
}
for (let j = 1; j < n; j++) {
// 初始化基准行:第一列
cur[0][j] = obstacleGrid[0][j] == 1 || cur[0][j - 1] == 0 ? 0 : 1
}
// 迭代
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
cur[i][j] = obstacleGrid[i][j] == 1 ? 0 : cur[i - 1][j] + cur[i][j - 1]
}
}
return cur[m - 1][n - 1]
}
本题重点:
另外上面三种解法:
的主要逻辑都是,下一次的结果从上次结果中推导出来。
也刷了不少动态规划的题,会发现:动态规范适用的类型是,题目的逻辑可以拆分成 n 个子逻辑的判断,而且子逻辑的结果之间还存在可以推导的关系