Leetcode 64 - Min path sum

Note:

  • DFS
    • Don’t worry about visiting a visited cell coz we use memo to remmeber the min path that goes through this cell.
  • DP
    • dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
    • Intialize first row and first col coz they don’t fit above deduction.

Question:

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:

img

1
2
3
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Code:

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* @param {number[][]} grid
* @return {number}
*/
var minPathSum = function(grid) {
const rows = grid.length;
const cols = grid[0].length;
let dp = [... new Array(rows)].map(e => new Array(cols).fill(Infinity));
dp[0][0] = grid[0][0];
for (let i = 1; i < rows; i++) {
dp[i][0] = dp[i-1][0] + grid[i][0];
}
for (let j = 1; j < cols; j++) {
dp[0][j] = dp[0][j-1] + grid[0][j];
}

for (let i = 1; i < rows; i++) {
for (let j = 1; j < cols; j++) {
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
return dp[rows-1][cols-1];
};