Solution to LeetCode 120 Triangle.
LeetCode 120
Triangle (Medium) [link]
Define dp[i][j] as the minimum path sum from top to the ith row and jth element. The recurrence relation is
dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]
Base case: dp[0][0] = triangle[0][0].
Note that the most left case: dp[i][0] = dp[i-1][0] + triangle[i][0]. The most right case : dp[i][i] = dp[i-1][i-1] + triangle[i][i]
Time complexity O(n^2). Space complexity O(n^2).
class Solution(object):
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
n = len(triangle)
dp = [[0] * n for _ in range(n)]
dp[0][0] = triangle[0][0]
for i in range(1, n):
dp[i][0] = dp[i - 1][0] + triangle[i][0]
for j in range(1, i):
dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]
dp[i][i] = dp[i - 1][i - 1] + triangle[i][i]
return min(dp[n - 1])
