Approach Summary
Bottom-up DP. Start from the second-to-last row. Each cell becomes val + min of the two adjacent cells below. Answer is triangle[0][0].
How to Recognize This Pattern
- "Minimum path sum from top to bottom of triangle"
- Bottom-up: each row reduces to min-path cost
Complexity Analysis
Time Complexity
O(n²)
Space Complexity
O(n)
Tags
Array Dynamic Programming