LeetCode: Triangle Solution

Memoized recursion

Implementation

1var minimumTotal = function (triangle) {
2  const memo = Array.from({ length: triangle.length }, _ =>
3    Array(triangle[triangle.length - 1].length).fill(null)
4  )
5
6  const recursion = (row, index) => {
7    if (memo[row][index] !== null) return memo[row][index]
8
9    if (row + 1 >= triangle.length) return triangle[row][index]
10
11    return (memo[row][index] =
12      triangle[row][index] +
13      // "if you are on index i on the current row, you may move to either index i or index i + 1 on the next row"
14      Math.min(recursion(row + 1, index), recursion(row + 1, index + 1)))
15  }
16
17  return recursion(0, 0)
18}