Triangle - Dynamic Programming / Knapsack

What is r and what is c?

“This is a classic problem for top-down dynamic programming or DFS + memoization.” yet the Java solution I believe is using bottom-up.

Hi, we updated the solution!

bottom up python
n = len(triangle)
dp = triangle[-1].copy()
for i in range(n-2, -1, -1):
m = len(triangle[i+1])
for j in range(m-1):
dp[j] = triangle[i][j] + min(dp[j], dp[j+1])

return dp[0]

Just to clear some confusion, “top-down vs. bottom-up” is not related to the direction in which we traverse the triangle (ie. start from 1st or last row).

We can see that whether use the initial orientation, or invert the triangle, the same intuition applies: track min from last row, add values from current row to it and take the min for next row.

Top-down refers to DFS and bottom-up refers to DP. Both solutions exist for both orientations of the triangle.

If we can edit input, we can do something like bfs but no need of a queue. We already have access to levels through index. Start editing from the bottom (size - 1) row to root.

public static int minimumTotal(List<List<Integer>> triangle) {
    if(triangle.size() == 0)
        return 0;
    if(triangle.size() == 1)
        return triangle.get(0).get(0);
    int minTotal = triangle.get(0).get(0);
    for(int i = triangle.size() - 2; i >= 0; i--){
        for(int j = 0; j < triangle.get(i).size(); j++){
            int minChild = Math.min(triangle.get(i+1).get(j),
            int node = triangle.get(i).get(j);
            triangle.get(i).set(j, node+minChild);
    return triangle.get(0).get(0);

Sharing Python solutions for both the approaches-

Uses Dynamic Programming
def minimum_total(triangle: List[List[int]]) -> int:
    # init dp array as the last row of the triangle
    dp = [triangle[-1][c] for c in range(len(triangle[-1]))]    

    for r in range(len(triangle)-2, -1, -1):
        for c in range(r+1):
            dp[c] = triangle[r][c] + min(dp[c], dp[c+1])
    return dp[0]

Uses DFS + Memoization
def minimum_total_DFS(triangle: List[List[int]]) -> int:
    def dfs(r, c): 
        if (r, c) in memo: 
            return memo[(r ,c)]

        if r == len(triangle)-1:   # reached the bottom
            return triangle[r][c]

        memo[(r ,c)] =  triangle[r][c] + min(dfs(r+1, c), dfs(r+1,c+1))
        return memo[(r ,c)] 

    memo = {}        
    return dfs(0,0)

I think the graph has some typos
5 6
11 10 11 13
15 12 11 18 12 19 21 16

Really appreciate this, this is the real DP solution.

Thanks for this DFS+Memoization solution!

Without any extra memory. Just update each entry in the triangle to hold its minimum path to the bottom of the triangle

using namespace std;

int minimum_total(std::vector<std::vector<int>> t) {
    for (int r = t.size() - 2; r >= 0; r--) {
        for(int c = 0; c <= r; c++ ) {
            t[r][c] +=  min(t[r + 1][c], t[r + 1][c + 1]); 
    return t[0][0];

test case 3 and 4 are wrong

This text in “DFS + Memoization” is incorrect: "or example, in the following diagram we see that the nodes labelled A and B depend on node C. ". Since it is a Top-Down solution, the C node should be the common child of node A and B, but the diagram shows C as the common parent.

My DFS solution:

from typing import List
from math import inf

def minimum_total(triangle: List[List[int]]) -> int:
    dp = []
    for i in range(len(triangle)):
        dp.append([inf] * (i+1))
    dp[0][0] = triangle[0][0]

    for i in range(1,len(triangle)):
        dp[i][-1] = dp[i-1][-1] + triangle[i][-1]    
        dp[i][0] = dp[i-1][0] + triangle[i][0]
        for j in range(1,len(dp[i])-1):
            smaller = min(dp[i-1][j],dp[i-1][j-1])
            dp[i][j] = smaller + triangle[i][j]
    return min(dp[-1])

my top down solution

def minimum_total(triangle: List[List[int]]) -> int:
    def dfs(r, c, memo):
        if r in memo and c in memo[r]:
            return memo[r][c]
        if r == len(triangle):
            return 0
        down_left = dfs(r + 1, c, memo) + triangle[r][c]
        down_right = dfs(r + 1, c + 1, memo) + triangle[r][c]
        result = min(down_left, down_right)
        if r not in memo:
            memo[r] = {}
        memo[r][c] = result
        return result
    return dfs(0, 0, {})