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) {
// WRITE YOUR BRILLIANT CODE HERE
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),
triangle.get(i+1).get(j+1));
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
2
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:
# WRITE YOUR BRILLIANT CODE HERE
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, {})
def minimum_total(triangle: List[List[int]]) → int:
# WRITE YOUR BRILLIANT CODE HERE
dp = triangle[-1]
for r in range(len(triangle)-2, -1, -1):
col_len = len(triangle[r])
for c in range(col_len):
dp[c] = triangle[r][c] + min(dp[c], dp[c+1])
return dp[0]
This is my bottomup approach and I find it very intuitive and readable. Since we are only concerned with the row below and the col number shrinks as we go up in the triangle, we only need to update the value of the dp[c] → where c corresponds to the col we are actually considering. Eventually, we get to the top where we are only interested in the c=1 and return the answer.
Java memory optimized solution with 1-dimension dp array:
public static int minimumTotal(List<List<Integer>> triangle) {
int[] dp = new int[triangle.get(triangle.size() - 1).size() + 1];
for (int row = triangle.size() - 1; row >= 0; row--) {
for (int level = 0; level < triangle.get(row).size(); level++) {
dp[level] = triangle.get(row).get(level) + Math.min(dp[level], dp[level + 1]);
}
}
return dp[0];
}
I solve it like this:
int minimum_total(std::vector<std::vector<int>> triangle) {
if(triangle.size() == 0)
{
return 0;
}
std::vector<std::vector<int>> arr;
arr.emplace_back(triangle.at(0));
for(int i = 1; i < triangle.size(); ++i)
{
std::vector<int> tmp(triangle.at(i).size(),
std::numeric_limits<int>::max());
for(int j = 0; j < arr.back().size(); ++j)
{
int adjacent_left = j;
int adjacent_right = j + 1;
tmp.at(adjacent_left) = std::min(tmp.at(adjacent_left),
arr.back().at(j) + triangle.at(i).at(adjacent_left));
tmp.at(adjacent_right) = std::min(tmp.at(adjacent_right),
arr.back().at(j) + triangle.at(i).at(adjacent_right));
}
arr.emplace_back(tmp);
}
return *std::min_element(arr.back().begin(), arr.back().end());
}
Apparently, at least in terms of speed, I also got n^2.