Given a triangle of numbers, find the minimum path sum from the top to the bottom. From each number, you may move to one of the two adjacent numbers in the row below.
DSA Animator › DSA Revision › Dynamic Programming › Triangle
Remember: bottom up removes all the edge cases of top down. Each cell picks the better of its two children. The video solves Triangle (LeetCode 120, Medium) with the Bottom-Up DP pattern from the Dynamic Programming topic, and you can replay every step in the interactive Triangle animation.
Given a triangle of numbers, find the minimum path sum from the top to the bottom. From each number, you may move to one of the two adjacent numbers in the row below.
For the triangle 2, then 3 4, then 6 5 7, then 4 1 8 3, the answer is 11. The path is 2, 3, 5, 1.
Trying every top to bottom path doubles the work with every row. There are 2 to the power of the height of paths.
Work from the bottom row upwards. Start with a copy of the last row, which is the best cost from each bottom position. For each number above, add the smaller of its two children below. Each row shrinks by one, and after the top row, a single value is left. That value is the minimum path sum.
Start from the bottom row: 4, 1, 8, 3. For the row 6, 5, 7: 6 plus 1 is 7, 5 plus 1 is 6, and 7 plus 3 is 10. For the row 3, 4: 3 plus 6 is 9, and 4 plus 6 is 10. For the top: 2 plus 9 is 11. The minimum path sum is 11, along 2, 3, 5, 1.
In code, copy the last row into a dp array. Loop the rows from the second last up to the top. For each index i, set dp of i to the value plus the smaller of dp of i and dp of i plus 1. Return dp of 0, so it's O of n squared time and O of n space.
Remember: bottom up removes all the edge cases of top down. Each cell picks the better of its two children.