120 Triangle 9 24 2025

120 Triangle.

Core Idea: Work backwards from bottom to top, at each position asking "what's the cheapest way to reach the bottom from here?"

How it Works:
1. Start from second-to-last row and move upward
2. For each position, look at the two positions directly below it
3. Add the smaller value from below to the current position
4. The top position ends up containing the minimum total path sum

Key Insights:

🔄 Bottom-Up Strategy: Instead of figuring out all possible paths from top to bottom, we work backwards, each position "knows" the cheapest route to the bottom.

🎯 Local Decisions: At each spot, we only need to make one simple choice: "which of my two downward neighbors gives me a cheaper path to the bottom?"

💾 In-Place Updates: We modify the triangle as we go, so each position stores the minimum cost to reach the bottom from that position.

🏁 Final Answer: When we're done, triangle[0][0] contains the minimum path sum from top to bottom.

The algorithm transforms each number into "minimum cost to reach bottom from here."