# LeetCode: Triangle Solution

Memoized recursion

## Implementation

```.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}var 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}```

Original problem

## Tags

leetcode

recursion

dynamic programming

## Next Post

LeetCode: Brick Wall

Apr 22, 2021

Search Posts