# Writing a more Pythonic solution to the min triangle path

The problem I'm referring to is available here. In quick summary, the problem gives a list of lists such as [,[3,4],[6,5,7],[4,1,8,3]] and we must find the minimum path sum: 2 + 3 + 5 + 1 = 11. I took the obvious DP approach:

def minimumTotal(self, triangle):
# make a memo with n rows and i columns
# where i is the number of elements in the last row
n, i = len(triangle), len(triangle[-1])
memo = [ * i for _ in range(n)]
memo = triangle
for m in range(1, n):
for k in range(m + 1):
if (k == 0):
memo[m][k] = triangle[m][k] + (memo[m-1] if m - 1 >= 0 else float("inf"))
elif (m == k):
memo[m][k] = triangle[m][k] + (memo[m-1][k-1] if m - 1 >= k - 1 else float("inf"))
else:
memo[m][k] = triangle[m][k] + min(memo[m-1][k-1] if m - 1 >= k - 1 else float("inf"), memo[m-1][k] if m - 1 >= k else float("inf"))
# now loop through the last row and choose the min
for l in range(1,i):


This code is faster than 95% of the other submission times so I'm satisfied with run time. However, what I am interested in is how to (a.) make this code more "Pythonic" and (b.) how to improve the memory usage. This code is more memory efficient than only 8% of submissions so I'm curious on how to better improve this.

• Drop the parens around your if conditions. – Reinderien Mar 8 '19 at 5:50

Your memo array is pretty inefficient, as it is of size $$\n^2\$$. There's a lot of wasted cells there, right? So one idea to improve the space complexity would be for each memo[i] to be just the right length. For example, memo would be an array of length 1 instead of length n.. This would reduce space complexity from $$\n^2\$$ to $$\n(n+1)/2\$$. Still quadratic, but a small improvement.

But you can see that you don't need to keep all that information. All you care about is the previous row, so there's no need to keep more history than that. You could have an array of length n that represents the previous state and reuse it as you go through the triangle. This would result in a space complexity of $$\O(n)\$$, a big improvement. Of course, if you could change the input in place you could do a space complexity of $$\O(1)\$$ - no extra space required :)

I also like to use a bottom up approach to these problems. It's more beautiful, as it makes the solution just bubble up. It would rid you of the last for loop as well, which would make it just a bit faster.

Here's a sketch:

t = [v for v in triangle[-1]]
for i in range(len(triangle) - 2, -1 , -1):
for j in range(len(triangle[i])):
t[j] = min(t[j], t[j + 1]) + triangle[i][j]

return t