My Muri Life

切换主题

本页目录

路径问题篇 ​

不同路径 ​

剑指 Offer II 098. 不同路径

  • 状态定义：dp[i][j] = x，表示从[0, 0]出发到[i,j]的不同路径数为x；
  • base case：dp[i][0] = dp[0][i] = 1；
  • 状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]。
JavaScript
const uniquePaths = (m, n) => {
  const dp = Array(m).fill(0).map(_ => Array(n).fill(0))
  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]
}

时间复杂度：O(mn)；空间复杂度：O(mn)。

不同路径 II ​

63. 不同路径 II

  • 状态定义：dp[i][j] = x，表示从[0, 0]出发到[i,j]的不同路径数为x；
  • base case：dp[0][0] = 1，并根据障碍物情况初始化第一行第一列；
  • 状态转移方程：dp[i][j] = grid[i][j] === 1 ? 0 : dp[i-1][j] + dp[i][j-1]。
JavaScript
const uniquePathsWithObstacles = grid => {
  if (grid[0][0] === 1) return 0
  const [m, n] = [grid.length, grid[0].length]
  const dp = Array(m).fill(0).map(_ => Array(n).fill(0))
  dp[0][0] = 1
  for (let i = 1; i < m; i++) {
    dp[i][0] = grid[i][0] === 1 || dp[i - 1][0] === 0 ? 0 : 1
  }
  for (let i = 1; i < n; i++) {
    dp[0][i] = grid[0][i] === 1 || dp[0][i - 1] === 0 ? 0 : 1
  }
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = grid[i][j] === 1 ? 0 : dp[i - 1][j] + dp[i][j - 1]
    }
  }
  return dp[m - 1][n - 1]
}

时间复杂度：O(mn)；空间复杂度：O(mn)。

最小路径和 ​

剑指 Offer II 099. 最小路径和

  • 状态定义：dp[i][j] = x，表示从[0, 0]出发到[i,j]的最小路径和为x；
  • base case：dp[0][0] = grid[0][0]，并初始化第一行第一列；
  • 状态转移方程：dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。
JavaScript
const minPathSum = grid => {
  const [m, n] = [grid.length, grid[0].length]
  const dp = Array(m).fill(0).map(_ => Array(n).fill(0))
  dp[0][0] = grid[0][0]
  for (let i = 1; i < m; i++) {
    dp[i][0] = dp[i - 1][0] + grid[i][0]
  }
  for (let i = 1; i < n; i++) {
    dp[0][i] = dp[0][i - 1] + grid[0][i]
  }
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
    }
  }
  return dp[m - 1][n - 1]
}

时间复杂度：O(mn)；空间复杂度：O(mn)。

最小路径和 II ​

174. 地下城游戏

  • 状态定义：dp[i][j] = x，表示从矩形终点出发到[i,j]的最小初始值为x；
  • base case：dp[m - 1][n] = dp[m][n - 1] = 1；
  • 状态转移方程：dp[i][j] = Math.max(1, Math.min(dp[i + 1][j], dp[i][j + 1]) - grid[i][j])。
JavaScript
const calculateMinimumHP = grid => {
  const [m, n] = [grid.length, grid[0].length]
  const dp = Array(m + 1).fill(0).map(_ => Array(n + 1).fill(Number.MAX_SAFE_INTEGER))
  dp[m - 1][n] = dp[m][n - 1] = 1
  for (let i = m - 1; i >= 0; i--) {
    for (let j = n - 1; j >= 0; j--) {
      dp[i][j] = Math.max(1, Math.min(dp[i + 1][j], dp[i][j + 1]) - grid[i][j])
    }
  }
  return dp[0][0]
}

时间复杂度：O(mn)；空间复杂度：O(mn)。

三角形最小路径和 ​

剑指 Offer II 100. 三角形最小路径和

  • 状态定义：dp[i][j] = x，表示从三角形最底层出发到[i,j]的最小路径和为x；
  • base case：dp[h - 1][i] = triangle[h - 1][i]；
  • 状态转移方程：dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]。
JavaScript
const minimumTotal = triangle => {
  const h = triangle.length
  const dp = Array(h).fill(0).map((_, idx) => Array(triangle[idx].length).fill(0))
  for (let i = 0; i < triangle[h - 1].length; i++) {
    dp[h - 1][i] = triangle[h - 1][i]
  }
  for (let i = h - 2; i >= 0; i--) {
    for (j = 0; j < triangle[i].length; j++) {
      dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]
    }
  }
  return dp[0][0]
}

时间复杂度：O(h^2)；空间复杂度：O(h)。