You are given a triangle as a list of rows, where row i has i + 1 numbers. Start at the top and move down one row at a time; from index j you may step to index j or j + 1 in the next row. Return the smallest possible sum of a path from the top to the bottom row.
- 1 <= triangle.length <= 200
- triangle[i].length == i + 1
- -10^4 <= triangle[i][j] <= 10^4
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Trying every path is O(2^n) because each step has two choices. But many paths share the same tail, so we use DP. State: dp[j] is the minimum sum from cell (i, j) to the bottom row. Recurrence: dp[j] = triangle[i][j] + min(dp[j], dp[j+1]), where the right side still holds the values of row i+1. Base case: for the last row, dp[j] is just the cell value. Working bottom up means every cell has exactly two children and no edge cases, and after reaching the top dp[0] is the answer.
Algorithm
- Copy the last row into
dp. - For rows
ifrom second last up to 0, andjfrom 0 toi:dp[j] = triangle[i][j] + min(dp[j], dp[j+1]). - Going left to right is safe because
dp[j+1]is still from the row below when you read it. - Return
dp[0].
O(n^2), every cell onceSpace: O(n) extraclass Solution: def minimumTotal(self, triangle: List[List[int]]) -> int: dp = list(triangle[-1]) # best sums from the bottom row for i in range(len(triangle) - 2, -1, -1): row = triangle[i] for j in range(i + 1): # dp[j] and dp[j + 1] still describe row i + 1 dp[j] = row[j] + min(dp[j], dp[j + 1]) return dp[0]