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)] # add the base case 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 answer = memo[-1] 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.