Teaching Kids Programming – Dynamic Programming Algorithm to Compute the Triangle Minimum Path Sum

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 3

The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

Example 2:
Input: triangle = [[-10]]
Output: -10

Follow 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) —