Problem statement

https://leetcode.com/problems/triangle/

Solution

Let dp(i, j) be the answer to the question: what is the minimum length of path, ending in i-th line and j-th element of this line. Then we can have two options:

  1. If we reached the last line, we do not have options to go next, so we just return triangle[i][j].
  2. If we did not reached the last line, we can go either to (i + 1, j) or to (i +1, j + 1), so we choose the minumum of two this values.

Complexity

Time and space complexity is O(n^2), because we have this number of states and only 2 transactions from one state. Note, that space complexity can be reduced to O(n), because in fact we need only last line, or it can be even reduced to O(1) if we allowed to change original triangle.

Code

class Solution:
    def minimumTotal(self, triangle):
        
        @lru_cache(None)
        def dp(i, j):
            if i == len(triangle) - 1: return triangle[i][j]
            return min(dp(i+1, j), dp(i+1, j+1)) + triangle[i][j]
        
        return dp(0, 0)