Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle


[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]


The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Difficulty: interview

Starter code:

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        

Solutions:
class Solution:
     def minimumTotal(self, triangle):
         """
         :type triangle: List[List[int]]
         :rtype: int
         """
         length = len(triangle)
         for i in range(length - 1, 0, -1):
             for j in range(1, len(triangle[i])):
                 if triangle[i][j] < triangle[i][j-1]:
                     triangle[i-1][j-1] += triangle[i][j]
                 else:
                     triangle[i-1][j-1] += triangle[i][j - 1]
         return triangle[0][0]

class Solution:
     """
     def minmum(self, triangle, i, j):
         if (i + 1) == len(triangle):
             return triangle[i][j]
         return min(self.minmum(triangle, i+1, j), self.minmum(triangle, i+1, j+1)) + triangle[i][j]
     """
     
     def minimumTotal(self, triangle):
         """
         :type triangle: List[List[int]]
         :rtype: int
         """
         #return self.minmum(triangle, 0, 0)
         
         rows = len(triangle)
         minPath = triangle[rows-1]
         for i in range(rows-1)[::-1]:
             for j in range(i+1):
                 minPath[j] = min(minPath[j], minPath[j+1]) + triangle[i][j]
         return minPath[0]
         


class Solution:
     def minimumTotal(self, triangle):
         """
         :type triangle: List[List[int]]
         :rtype: int
         """
         
         for i in range(1,len(triangle)):
             for j in range(i+1):
                 if j == 0:
                     triangle[i][j] += triangle[i-1][0]
                 elif j == i:
                     triangle[i][j] += triangle[i-1][-1]
                 else:
                     triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j])
         return min(triangle[-1])


class Solution:
     def minimumTotal(self, triangle):
         """
         :type triangle: List[List[int]]
         :rtype: int
         """
         
         for i in range(1,len(triangle)):
             triangle[i][0] = triangle[i][0] + triangle[i-1][0]
             triangle[i][-1] = triangle[i][-1] + triangle[i-1][-1]
             for j in range(1,len(triangle[i])-1):
                 triangle[i][j] = min(triangle[i-1][j-1], triangle[i-1][j]) + triangle[i][j]
                 
         return min(triangle[-1])

class Solution:
     def minimumTotal(self, triangle):
         """
         :type triangle: List[List[int]]
         :rtype: int
         """
         length = len(triangle)
         dp = []
         for i in range(length):
             dp.append([])
             for j in range(len(triangle[i])):
                 dp[i].append(float('inf'))
         dp[0][0] = triangle[0][0]
         for i in range(1, length):
             dp[i][0] = dp[i-1][0] + triangle[i][0]
             dp[i][-1] = dp[i-1][-1] + triangle[i][-1]
         
         for i in range(1, length):
             for j in range(1, len(triangle[i]) - 1):
                 dp[i][j] = min(dp[i][j], dp[i-1][j] + triangle[i][j], dp[i-1][j-1] + triangle[i][j])
         return min(dp[length-1])

class Solution:
     def minimumTotal(self, triangle):
         mini = 100000000
         level =0 
         while level < (len(triangle)-1):
             for i in range(len(triangle[level+1])):
                 if i==0 :
                     triangle[level+1][i] += triangle[level][i]
                 elif i == len(triangle[level]):
                     triangle[level+1][i] += triangle[level][i-1]
                 else :
                     triangle[level+1][i] += min(triangle[level][i-1], triangle[level][i])
                     
             level +=1
         
         return  min(triangle[len(triangle)-1])
             
         
 
         """
         :type triangle: List[List[int]]
         :rtype: int
         """


class Solution:
     '''
     def minimumTotal(self, triangle):
         cost = [[0 for j in range(len(i))] for i in triangle]
         for row in range(len(triangle)):
             for col in range(len(triangle[row])):
                 if row == 0:
                     cost[row][col] = triangle[row][col]
                 else:
                     if col-1 >= 0 and col < len(triangle[row-1]):
                         cost[row][col] = min(cost[row-1][col-1]+triangle[row][col],cost[row-1][col]+triangle[row][col])
                     elif col-1 >= 0:
                         cost[row][col] = cost[row-1][col-1]+triangle[row][col]
                     elif col < len(triangle[row-1]):
                         cost[row][col] = cost[row-1][col]+triangle[row][col]
         return min(cost[len(triangle)-1])
     '''
     #O(n) extra space:
     def minimumTotal(self, triangle):
         cost = [[0 for j in range(len(triangle))] for i in range(2)]
         for row in range(len(triangle)):
             for col in range(len(triangle[row])):
                 if row == 0:
                     cost[row][col] = triangle[row][col]
                 else:
                     if col-1 >= 0 and col < len(triangle[row-1]):
                         cost[row%2][col] = min(cost[(row-1)%2][col-1]+triangle[row][col],cost[(row-1)%2][col]+triangle[row][col])
                     elif col-1 >= 0:
                         cost[row%2][col] = cost[(row-1)%2][col-1]+triangle[row][col]
                     elif col < len(triangle[row-1]):
                         cost[row%2][col] = cost[(row-1)%2][col]+triangle[row][col]
         return min(cost[(len(triangle)-1)%2])

class Solution:
     def nodeSum(self, L, U):
         ans = [0]*len(U)
         for i,v in enumerate(U):
             ans[i] = (v+min(L[i],L[i+1]))
         return ans
     
     def minimumTotal(self, triangle):
         """
         :type triangle: List[List[int]]
         :rtype: int
         """
         L = triangle[-1]
         for i in range(len(triangle)-1, 0, -1):
             L=self.nodeSum(L, triangle[i-1])
         return L[0]

class Solution:
     def minimumTotal(self, triangle):
         row = [triangle[0][0]]
         for i in range(1, len(triangle)):
             new_row = []
             for j in range(len(row)+1):
                 new_row.append(triangle[i][j]+min(row[j-1] if j-1>=0 else sys.maxsize, row[j] if j<len(row) else sys.maxsize))
             row = new_row
         return min(row)


class Solution:
     def minimumTotal(self, triangle):
         """
         :type triangle: List[List[int]]
         :rtype: int
         """
         res = [0]
         for row in triangle:
             res = [row[i]+min([res[j] for j in (i-1, i) if 0<=j<len(res)]) for i in range(len(row))]
         return min(res)


class Solution:
     def minimumTotal(self, triangle):
         import math
         """
         :type triangle: List[List[int]]
         :rtype: int
         """
         cost = {(-1, -1): math.inf, (-1,0):0, (-1, 1):math.inf}
         for i in range(len(triangle)):
             cost[(i, -1)] = math.inf
             cost[i, len(triangle[i])] = math.inf
 
         for i in range(len(triangle)):
             for j in range(len(triangle[i])):
                 cost[(i, j)] = triangle[i][j] + min(cost[(i-1, j)], cost[(i-1, j-1)])
                 
         return min([cost[(len(triangle)-1, j)] for j in range(len(triangle[-1]))])

class Solution:
     def minimumTotal(self, triangle):
         """
         :type triangle: List[List[int]]
         :rtype: int
         """
         layer_costs = triangle[-1]
         
         for layer in range(len(triangle)-2, -1, -1): # range(start, end +- 1, step)
             for pos in range(len(triangle[layer])):
                 min_cost = min(layer_costs[pos], layer_costs[pos+1]) + triangle[layer][pos]
                 layer_costs[pos] = min_cost
         
         return(layer_costs[0])

class Solution:
         
     def minimumTotal(self, triangle):
         """
         :type triangle: List[List[int]]
         :rtype: int
         """
         memory = []
         for i in range(len(triangle)):
             memory.append({})
         
         return self.helper(memory, triangle, 0, 0) 
 
     def helper(self, memory, triangle, i, j):
         if i >= len(triangle):
             return 0 
         
         if memory[i].get(j) is None:
             memory[i][j] = triangle[i][j] + \
                            min(self.helper(memory, triangle, i+1, j), self.helper(memory, triangle, i+1, j+1))
             
         return memory[i][j]

class Solution:
     def minimumTotal(self, triangle):
         """
         :type triangle: List[List[int]]
         :rtype: int
         """
         """
         For each position (column) C within a row R,
         the minimum path sum that leads to (r, c) is defined as:
         min_path_sum[r][c] = min(min_path_sum[r-1][adj] for adj in adjacent columns of (r,c)) + triangle[r][c]
         """
         
         if not triangle or not triangle[0]:
             return 0
         
         min_path_sum = [[0] * len(triangle) for row in range(len(triangle))]
         min_path_sum[0][0] = triangle[0][0]
         
         ROWS = len(triangle)
         
         
         def get_valid_adjacents_of(row, col):
             if col == 0:
                 return [(row - 1, col)]
             if col == row:
                 return [(row - 1, col - 1)]
             return [(row - 1, col - 1), (row - 1, col)]
         
         for row in range(1, ROWS):
             for col in range(0, row + 1):
                 adjacents = get_valid_adjacents_of(row, col)
                 min_path_sum[row][col] = triangle[row][col] + min(min_path_sum[r][c] for r, c in adjacents)
         
         return min(min_path_sum[-1])

class Solution:
     def minimumTotal(self, triangle):
         """
         :type triangle: List[List[int]]
         :rtype: int
         """
         if not triangle:
             return 0
         
         dp = triangle.pop()
         
         while triangle:
             level = triangle.pop()
             
             for i in range(len(level)):
                 dp[i] = min(dp[i], dp[i + 1]) + level[i]
                     
         return dp[0]

class Solution:
 	def minimumTotal(self, triangle):
 		self._min_cache = {} 
 		for i in reversed(list(range(len(triangle)))):
 			for j in reversed(list(range(len(triangle[i])))):
 				self.get_minimum_sum(triangle, i, j)
 		return self.get_minimum_sum(triangle, 0, 0)
 
 	def get_minimum_sum(self, triangle, level_i, item_j):
 		if ((level_i, item_j) in self._min_cache):
 			return self._min_cache[(level_i, item_j)]
 		if level_i < 0 or level_i >= len(triangle):
 			return 0
 		level = triangle[level_i]
 
 		if item_j<0 or item_j>len(level):
 			return 0
 
 		item = level[item_j]
 
 		min_v = item+min(self.get_minimum_sum(triangle,level_i+1,item_j),
 					    self.get_minimum_sum(triangle,level_i+1,item_j+1))
 		self._min_cache[(level_i, item_j)] = min_v
 
 		return min_v