Dynamic Programming: 120. Triangle

6 min readMar 21, 2018

In today’s DP example, let’s take a look at problem #120 Triangle from LeetCode. Take a look at the original problem description if you need a better explanation, but in summary the problem is: Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

The first mistake people make with this question is they fail to understand that you cannot simply traverse down the triangle taking the lowest number (greedy approach).

Truths and Assumptions

The input indexes are tricky, let’s settle some conventions. For each row, we can refer to each number in the row based on it’s index n. Then we can say, for a given row m and index n, you have two possible indexes in the next row(m+1): n or n+1. This is because each row is larger than the proceeding row by exactly 1 element.
The rows start at the top, with index 0.
The inputs can contain duplicates and negative numbers!
We’ll assume the input is well formed for brevity sake.
It is not good enough to simply keep taking the smaller of the two numbers as you work down the tree. In some cases, it is required to take a higher number in order to gain access to a lower path sum. See image below:

Recursive Solution First

On each recursive call, we’re at a particular row m, we need to decide which item in the next row to take. I.e.

Take the left (n) or right (n+1) path. We can decide this by accepting lesser of the the minimum path sums starting at notes (n) and (n+1) for row m-1. This way we can keep breaking down the solution into smaller problems as we work our way down the tree.
Base Case: For the last row in the triangle, we the minimum path su mis the value itself.

public int minimumTotal(List<List<Integer>> triangle) {
   return findMinPath(triangle, 0, 0).intValue();
}public Integer findMinPath(List<List<Integer>> triangle, int rowNum, int index) {   List<Integer> row = triangle.get(rowNum);   // base case, we are at the last row
   if (rowNum == triangle.size() - 1) {
      return row.get(index);
   }   int currentValue = row.get(index);
   int maxSumLeft = findMinPath(triangle, rowNum + 1, index);
   int maxSumRight = findMinPath(triangle, rowNum + 1, index + 1);   return currentValue + Math.min(maxSumLeft, maxSumRight);
}

Analyse the Recursive Solution

At each recursion call, we need to make the decision to traverse down the left or right path. Because of this, it is possible to reach any given node using two different paths. Looking at the recursion tree, we can see a duplicate calculation taking place for node with value 5 in the 3rd row.

Runtime complexity: O(n) = 2^n where n is the number of elements.

Recursive Solution First With Memorization

The fact that there are duplicate sub-trees makes it a candidate for memorization. The memorization function is indexed by two keys, the row number and index and will store the minimum path sum for the tree using this indexed number as a root.

public Integer findMinPath(List<List<Integer>> input, int rowNum, int index) {    List<Integer> row = input.get(rowNum);    // base case, we are at the last row
    if (rowNum == input.size() - 1) {
       return row.get(index);
    }    Integer cachedValue = memoTable[rowNum][index];
    if (cachedValue == null) {
       int currentValue = row.get(index);
       int maxSumLeft = findMinPath(input, rowNum + 1, index);
       int maxSumRight = findMinPath(input, rowNum + 1, index + 1);
       int sumPath = currentValue + Math.min(maxSumLeft, maxSumRight);
       memoTable[rowNum][index] = sumPath;
       return sumPath;
    }    return cachedValue;
}

Here we create a 2D memorization table which is indexed by the row number and index. This reduces the time complexity to O(n) because we traverse though a number along the path only once.

Dynamic Programming

Let’s consider the conditions for using DP to find an efficient solution:

Overlapping Sub-problems — Yes. We can see with our memorization algorithm that there are overlapping sub-problems.
Optimal Substructure — Yes. At each node in the call-tree, we are making the decision to go down the left or right path. The decision is based on the path sums for each sub-tree — for which we always select the smaller one.

The DP Table

We need to store the sum-path for a given sub-tree as the value in the table. Since the inputs to path sum function, f(m, n) = dp[m,n] takes the row number and index, they make good candidates for the table row and column. We’ll define the function v(m,n) to be the value for the number at row m index n.

Using this information, we get the following DP table:

The rows represent each level in the tree and columns are the indexes to numbers in the row

The bottom row (4) is the base case where the path sums for leaf nodes are the values themselves. We’ll work our way from the bottom row (which represents the bottom of the triangle) to the top.

Fill Row 3 {6, 5, 7}:

dp[2][0]: is min(dp[3,0], dp[3,1]) + v(2,0) = min(4,1)+6 = 7

dp[2][1]: is min(dp[3,1], dp[3,2]) + v(2,1) = min(1,8)+5 = 6

dp[2][2]: is min(dp[3,2], dp[3,3]) + v(2,2) = min(8,3)+7 = 10

Fill Row 2 {3, 4}:

dp[1][0]: is min(dp[1,0], dp[2,1]) + v(1,0) = min(7,6)+3 = 9

dp[1][1]: is min(dp[1,1], dp[2,2]) + v(1,1) = min(6,10)+4 = 10

Fill Row 1 {2}:

dp[0][0]: is min(dp[1,0], dp[1,1]) + v(0,0) = min(9,10)+2 = 11

Time Complexity

The DP solution runs in O(n) where n is the number of elements. The table consumes O(n*m) but that can be reduced to just m if you use a linked list. This understanding of linked list to reduce space complexity is important!

The Code

public Integer findMinPath(List<List<Integer>> triangle) {   int[][] dp = new int[triangle.size()][triangle.size()];   // init the first row
   List<Integer> lastRow = triangle.get(triangle.size() - 1);
   for (int i = 0; i < lastRow.size(); i++) {
      dp[triangle.size() - 1][i] = lastRow.get(i);
   }   for (int i = triangle.size() - 2; i > -1; i--) {      List<Integer> row = triangle.get(i);         for (int j = 0; j < row.size(); j++) {
            int maxSumLeft = dpTable[i + 1][j];
            int maxSumRight = dpTable[i + 1][j + 1];
            int currentValue = row.get(j);
            int sumPath = currentValue + Math.min(maxSumLeft, maxSumRight);
            dp[i][j] = sumPath;
      }
   }   return dp[0][0];
}

The tricky part of the DP programming solution is to get the indices correct. We start at the “bottom” of the table and work our way to the top (but the DP table can also be built inverted). I personally designed the DP array so it mimics the structure of the “triangle”. After the full DP table is built, the answer resides in the dp[0][0] cell. I would say this is a very straightforward DP problem as it both is easy to conceptually understand and has a very intuitive DP solution.

Click here to see my write up on the classic 0/1 knapsack problem.