Triangle
Medium · Dynamic Programming · about 15 minutes
Asked at Bloomberg, Amazon, Google, Microsoft, Meta, Apple, Optiver, Samsung, Sony, Jump Trading.
triangle is a list of rows where row i holds i + 1 numbers. Walk from the top to the bottom, moving at each step from position i to position i or i + 1 of the row below, and add up the numbers you pass. Return the smallest total possible.