Triangle
Given a triangle array, return the minimum path sum from top to bottom. For each step, you can move to an adjacent number.
Constraints:
- 1 <= triangle.length <= 200
- triangle[i].length <= i + 1
- -10^4 <= triangle[i][j] <= 10^4
Examples:
Input: [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11
Solutions
Dynamic Programming
The dynamic programming approach involves creating a 2D array dp where dp[i][j] represents the minimum path sum from the top to the current position. We initialize the first row of dp with the first row of the triangle. Then, for each row from the second to the last, we calculate the minimum path sum for each position by considering the minimum path sum of the two adjacent positions in the previous row and adding the current value. Finally, we return the minimum value in the last row of dp.
def minimumTotal(triangle):
n = len(triangle); dp = [[0]*n for _ in range(n)]; dp[0][0] = triangle[0][0]; for i in range(1, n):
for j in range(i+1):
if j == 0:
dp[i][j] = dp[i-1][j] + triangle[i][j]; elif j == i:
dp[i][j] = dp[i-1][j-1] + triangle[i][j]; else:
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]; return min(dp[-1])Follow-up:
What if the triangle is very large and we need to optimize the space complexity?
