-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.js
40 lines (35 loc) · 921 Bytes
/
index.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
/**
* @param {number[][]} path
* @returns number
*/
function getOptimalPath(path) {
const getMinimumSumPath = (row, column) => {
if (row === path.length) return 0
return (
path[row][column] +
Math.min(
getMinimumSumPath(row + 1, column),
getMinimumSumPath(row + 1, column + 1)
)
)
}
const optimalPath = getMinimumSumPath(0, 0)
return optimalPath
}
/**
* @param {number[][]} path
* @returns number
*/
function getOptimalPathOptimized(path) {
// const memory = path.pop()
// for (let i = path.length - 1; i >= 0; i--) {
// for (let j = 0; j < path[i].length; j++) {
// memory[j] = path[i][j] + Math.min(memory[j], memory[j + 1])
// }
// }
// return memory[0]
return path.reduceRight((previous, current) =>
current.map((v, i) => v + Math.min(previous[i], previous[i + 1]))
)[0]
}
export {getOptimalPath, getOptimalPathOptimized}