Minor Cleanup
Contrary to @Graipher's opinion, I find your max_triangle_sum implementation is reasonably clear. Although, I'm not sure I'd refer to it as dynamic programming; it is simply computing top-down the maximum sums for each row.
dp = [[-1] * row_index for row_index in range(1, height + 1)]
What does row_index mean? It doesn't convey any meaning other than the index number of the row. [-1] * row_index is ... mysterious. row_length conveys meaning: it is length of the row, and [-1] * row_length tells the reader you have a row of -1 values of a certain length.
What is the -1 mean? Where is it used? This statement creates a triangular data structure, with -1 at each cell, but only to allocate the structure. The actual -1 value is not used; it is unconditionally overwritten in the following code. If you have a mistake in the following code, it might use this -1 value, and quietly produce erroneous results. If you used None instead of -1, if you ever accidentally used the value in a cell before it has been assigned, Python would raise an exception.
dp = [[None] * row_length for row_length in range(1, height + 1)]
Avoid negative indexing.
dp[i][i] = dp[i-1][i-1] + triangle[i][-1]
Here, triangle[i][-1] is referring to the last cell on the ith row. But the cells on the ith row from from 0 to i, so triangle[i][-1] simply means triangle[i][i]. You are already assigning to dp[i][i], so this gives the statement a nice symmetry:
dp[i][i] = dp[i-1][i-1] + triangle[i][i]
You don't really need to pass height to max_triangle_sum: it can easily be computed as:
height = len(triangle)
Space
Because you are allocating dp to hold the values of sum of the paths to each cell of each row of the triangle, your solution takes \$O(N^2)\$ space to find the solution.
Consider these statements:
dp[i][0] = dp[i-1][0] + triangle[i][0]
dp[i][i] = dp[i-1][i-1] + triangle[i][-1]
dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]
dp[i][...] only depends upon values in d[i - 1][...]. This means you only need the previous dp row to compute the next dp row; you don't need the whole dp triangle structure, just two rows:
curr = [triangle[0][0]]
for i in range(1, height):
prev = curr
curr = [None] * (i + 1)
curr[0] = prev[0] + triangle[i][0]
curr[i] = prev[i - 1] + triangle[i][i]
for j in range(1, i):
curr[j] = max(prev[j - 1], prev[j]) + triangle[i][j]
As a bonus, this should be faster, since less indexing is being performed.
We've still got triangle[i] being indexed constantly. We can eliminate that by iterating over the rows of triangle directly. We'll use enumerate() so we keep the row index:
for i, row in enumerate(triangle[1:], 1):
prev = curr
curr = [None] * (i + 1)
curr[0] = prev[0] + row[0]
curr[i] = prev[i - 1] + row[i]
for j in range(1, i):
curr[j] = max(prev[j - 1], prev[j]) + row[j]
That's a little cleaner, and a little faster.
Now the ugliest part having to handle the first and last value separately. The problem is there is no value before the first element, and no value after the last element to compute the max() on. But why isn't there? Or more to the point, why can't there be? If you padded the previous row with duplicated first and last values, you'd turn those special cases into the regular case of a value in the middle of the row:
for i, row in enumerate(triangle[1:], 1):
prev = [curr[0]] + curr + [curr[-1]] # Duplicate first & last values
curr = [None] * (i + 1)
for j in range(0, i + 1):
curr[j] = max(prev[j], prev[j + 1]) + row[j]
Note: I've had to change prev[j-1] and prev[j] to prev[j] and prev[j + 1] to account for the changed indices, due to the duplicated value at the start.
Now, we are filling in all the values of curr in a simple for loop. This screams list comprehension. No need to allocate the curr list ahead of time anymore.
for i, row in enumerate(triangle[1:], 1):
prev = [curr[0]] + curr + [curr[-1]] # Duplicate first & last values
curr = [max(prev[j], prev[j + 1]) + row[j] for j in range(0, i + 1) ]
But we're still doing a lot of indexing. We've got prev[j], and row[j] which are normalish indexes, and we've got prev[j + 1] which could be considered adjusted_prev[j] if we assigned adjusted_prev the values of prev[1:]. Then, with all the values being retrieved by a simple [j] index, we can let Python do the indexing for us but turning the indexing into iteration. Finally, since Python knows the number of values in the lists, we no longer need the i index:
for row in triangle[1:]:
prev = [curr[0]] + curr + [curr[-1]] # Duplicate first & last values
curr = [max(a, b) + x for a, b, x in zip(prev[:-1], prev[1:], row) ]
Since prev[:-1] gives us all the values of the curr with the first value duplicated, and prev[1:] gives us all the values of curr with the last value duplicated, we don't even need prev:
def max_triangle_sum(triangle):
curr = [triangle[0][0]]
for row in triangle[1:]:
curr = [max(a, b) + x for a, b, x in zip([curr[0]] + curr, curr + [curr[-1]], row)]
return max(curr)
The space requirement (ignoring triangle) is now \$O(N)\$, since only the previous row needs to be held in memory while the current row is being computed.
If it is guaranteed that the triangle only contains positive numbers, and since max(0, x) == x whenever x is positive, then instead of duplicating the first and last values, we could append and prepend a zero to each end. This will allow us to remove the first row as a special case:
def max_triangle_sum(triangle):
curr = []
zero = [0]
for row in triangle:
curr = [max(a, b) + x for a, b, x in zip(zero + curr, curr + zero, row)]
return max(curr)
Now, triangle doesn't even need to be held in memory. Instead, an iterable object could be passed in, which could read the triangle in line by line on demand, further ensuring an \$O(N)\$ memory solution.
See other answers for great feedback on input sanitization, and reading the triangle data from a file.
