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.

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

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

Solutions:
class Solution:

	def minimumTotal(self, triangle):
		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 minimumTotal(self, triangle):
		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):
		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])


class Solution:

	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]
				elif 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):
		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):
		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
		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):
		layer_costs = triangle[-1]
		for layer in range(len(triangle) - 2, -1, -1):
			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):
		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):
		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):
		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