Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

64. 最小路径和 #51

Open
Geekhyt opened this issue Apr 20, 2021 · 0 comments
Open

64. 最小路径和 #51

Geekhyt opened this issue Apr 20, 2021 · 0 comments
Labels

Comments

@Geekhyt
Copy link
Owner

Geekhyt commented Apr 20, 2021

原题链接

状态定义

dp[i][j] 代表从 (0, 0) 走到 (i, j) 的最小路径和。

状态转移方程

明确题意:只能向右或者向下走,也就是说终点 (i, j) 只能从 (i - 1, j) 或者 (i, j - 1) 走过来。

分为以下三种情况分别处理:

  1. 左边或者上边都是边界时,终点也就是起点。
  • dp[i][j] = grid[i][j]
  1. 左边或者上边为边界时:
  • grid[i][j] = grid[i - 1][j] + grid[i][j]
  • grid[i][j] = grid[i][j - 1] + grid[i][j]
  1. 左边和上边都不为边界时:
  • grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]
const minPathSum = function(grid) {
  const n = grid.length
  const m = grid[0].length
  const dp = Array.from(new Array(n), () => new Array(m))
  for (let i = 0; i < n ; i++) {
    for (let j = 0; j < m; j++) {
      if (i !== 0 && j !== 0) {
        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
      } else if (i !== 0 && j === 0) {
        dp[i][j] = dp[i - 1][j] + grid[i][j]
      } else if (i === 0 && j !== 0) {
        dp[i][j] = dp[i][j - 1] + grid[i][j]  
      } else if (i === 0 && j === 0) {
        dp[i][j] = grid[i][j]
      }
    }
  }
  return dp[n - 1][m - 1]
}
  • 时间复杂度: O(m * n)
  • 空间复杂度: O(m * n)

降维

不需要额外建立空间,直接遍历修改 grid[i][j]

const minPathSum = function(grid) {
  const n = grid.length
  const m = grid[0].length
  for (let i = 0; i < n ; i++) {
    for (let j = 0; j < m; j++) {
      if (i !== 0 && j !== 0) {
        grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]
      } else if (i !== 0 && j === 0) {
        grid[i][j] = grid[i - 1][j] + grid[i][j]
      } else if (i === 0 && j !== 0) {
        grid[i][j] = grid[i][j - 1] + grid[i][j]  
      } else if (i === 0 && j === 0) {
        grid[i][j] = grid[i][j]
      }
    }
  }
  return grid[n - 1][m - 1]
}
  • 时间复杂度: O(m * n)
  • 空间复杂度: O(1)
@Geekhyt Geekhyt added the 中等 label Jun 2, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant