Teaching Kids Programming: Videos on Data Structures and Algorithms
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.
Example 1:
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 3The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).
Example 2:
Input: triangle = [[-10]]
Output: -10Follow up: Could you do this using only O(n) extra space, where n is the total number of rows in the triangle?
Bottom-up Dynamic Programming Algorithm to Compute the Minimum Path Sum
The minimum path sum is the same if you calculate it top to bottom, or bottom to top. Thus, the Dynamic Programming transistion function is:
We can overwrite the existing Triangle, from bottom-to-up, from left to right.
1 2 3 4 5 6 7 | class Solution: def minimumTotal(self, triangle: List[List[int]]) -> int: for row in range(len(triangle) - 2, -1, -1): for col in range(len(triangle[row])): triangle[row][col] = min(triangle[row + 1][col], \ triangle[row + 1][col + 1]) + triangle[row][col] return triangle[0][0] |
class Solution: def minimumTotal(self, triangle: List[List[int]]) -> int: for row in range(len(triangle) - 2, -1, -1): for col in range(len(triangle[row])): triangle[row][col] = min(triangle[row + 1][col], \ triangle[row + 1][col + 1]) + triangle[row][col] return triangle[0][0]
The minimum path sum will then be at T[0][0]. The time complexity is O(RC) and the space complexity is O(1) as we are using the given Triangle to store the intermediate min path sum
Top Down Dynamic Programming Algorithm to Compute the Minimum Triangle Path Sum
We can compute the DP function value by Recursion with Memoization – that is the Top Down Dynamic Programming:
1 2 3 4 5 6 7 8 | class Solution: def minimumTotal(self, triangle: List[List[int]]) -> int: @cache def f(r, c): if r == len(triangle) - 1: return triangle[r][c] return min(f(r + 1, c), f(r + 1, c + 1)) + triangle[r][c] return f(0, 0) |
class Solution: def minimumTotal(self, triangle: List[List[int]]) -> int: @cache def f(r, c): if r == len(triangle) - 1: return triangle[r][c] return min(f(r + 1, c), f(r + 1, c + 1)) + triangle[r][c] return f(0, 0)
See also: Teaching Kids Programming – Dynamic Programming Algorithms to Count Numbers with Unique Digits
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Algorithm to Valid N Queens
Next Post: Develop a Load Balancer using AWS Lambda