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}

References

Original problem

Comments

Loading comments...

Tags

leetcode

recursion

dynamic programming

Next Post

LeetCode: Brick Wall

Apr 22, 2021

HoningJS

Search Posts