Problem
Given a triangle array, return the minimum path sum from top to bottom.
For each step, you may move to an adjacent number of the row below. More formally, 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.
Testcases
Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
2
3 4
6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).
Initial Result
Time spent: 28 min
Fail. Passed most cases but faced a TLE and tried incorrect DP.
Initial Approach
I approached the problem as a backtracking problem (shortest-path to bottom row). This is not inherently wrong, but it ignores the DP abilities of our given matrix.
What I Missed
We can use DP by storing summations of the existing path in each cell and building our path lengths in the bottom row.
Approach to the Solution
From the second row down, store the minimum sum of the two: your upstairs neighbor and the one to the left of them. This greedy step allows you to get the minimum sum to this cell (and therefore including this cell) at each cell. This makes the bottom row contain the minimums to the bottom for each bottom cell; the lowest of those values is our answer.
Key Takeaways
Draw out any graph traversal problems. Focus on DP situations that use given data structures (usually matrices).