-
Notifications
You must be signed in to change notification settings - Fork 21
/
MinimumPathSum.js
94 lines (83 loc) · 1.97 KB
/
MinimumPathSum.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/**
* 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 1:
* [[1,3,1],
* [1,5,1],
* [4,2,1]]
* Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum.
*
* Accepted.
*/
/**
* @param {number[][]} grid
* @return {number}
*/
let minPathSum = function (grid) {
if (grid.length === 0) {
return 0;
}
if (grid.length === 1) {
if (grid[0].length === 0) {
return 0;
}
if (grid[0].length === 1) {
return grid[0][0];
}
}
let matrix = new Array(grid.length);
for (let i = 0; i < grid.length; i++) {
matrix[i] = new Array(grid[0].length);
}
matrix[0][0] = grid[0][0];
for (let i = 1; i < grid.length; i++) {
matrix[i][0] = matrix[i - 1][0] + grid[i][0];
}
for (let i = 1; i < grid[0].length; i++) {
matrix[0][i] = matrix[0][i - 1] + grid[0][i];
}
for (let i = 1; i < grid.length; i++) {
for (let j = 1; j < grid[0].length; j++) {
matrix[i][j] = Math.min(matrix[i - 1][j] + grid[i][j], matrix[i][j - 1] + grid[i][j]);
}
}
return matrix[grid.length - 1][grid[0].length - 1];
};
if (minPathSum([]) === 0) {
console.log("pass")
} else {
console.error("failed")
}
if (minPathSum([[]]) === 0) {
console.log("pass")
} else {
console.error("failed")
}
if (minPathSum([[1]]) === 1) {
console.log("pass")
} else {
console.error("failed")
}
// Expected: 7
// The matrix:
// 1 4 5
// 2 7 6
// 6 8 7
if (minPathSum([[1, 3, 1], [1, 5, 1], [4, 2, 1]]) === 7) {
console.log("pass")
} else {
console.error("failed")
}
// Expected: 5
// The matrix:
// 1 2 3
// 2 4 4
// 3 6 5
if (minPathSum([[1, 1, 1], [1, 2, 1], [1, 3, 1]]) === 5) {
console.log("pass")
} else {
console.error("failed")
}