2
\$\begingroup\$

The problem I'm referring to is available here. In quick summary, the problem gives a list of lists such as [[2],[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 = [[0] * i for _ in range(n)]
    # add the base case 
    memo[0][0] = triangle[0][0]
    for m in range(1, n):
        for k in range(m + 1):
            if (k == 0):
                memo[m][k] = triangle[m][k] + (memo[m-1][0] 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
    answer = memo[-1][0]
    for l in range(1,i):
        if (memo[-1][l] < answer):
            answer = memo[-1][l]
    return answer

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.

\$\endgroup\$
  • \$\begingroup\$ Drop the parens around your if conditions. \$\endgroup\$ – Reinderien Mar 8 '19 at 5:50
3
\$\begingroup\$

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[0] 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[0]
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.