Triangle

Description

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Solution(javascript)

const minimumTotal = (triangle = []) => {
  const memo = {}
  const aux = (columIndex, rowIndex) => {
    memo[columIndex] = memo[columIndex] || {}
    if (memo[columIndex][rowIndex] !== undefined) {
      return memo[columIndex][rowIndex]
    }
    if (columIndex === triangle.length - 1) {
      return triangle[columIndex][rowIndex]
    }
    memo[columIndex][rowIndex] = Math.min(
      aux(columIndex + 1, rowIndex) + triangle[columIndex][rowIndex],
      aux(columIndex + 1, rowIndex + 1) + triangle[columIndex][rowIndex],
    )
    return memo[columIndex][rowIndex]
  }
  return aux(0, 0)
}