Given a triangle array, return the minimum path sum to reach from top to bottom.
For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.
Example 1:
Input:
n = 4
triangle = [[2],
           [3,4],
          [6,5,7],
         [4,1,8,3]]
Output:
11
Explanation:
     2
   3 4
  6 5 7
 4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11.
Example 2:
Input:
n =  1
triangle = [[10]]
Output:
10
Your Task:
You don't have to read input or print anything. Your task is to complete the function minimizeSum() which takes integer n and the triangle and returns the minimum sum to reach from top to bottom.
Constraint:
1 <= triangle.length <= 200
triangle[i].length =  triangle[i-1].length + 1
1 <= triangle[i][j] <= 1000
Expected Time Complexity: O(n * n)
Expected Space Complexity: O(n* n)

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

    def minimizeSum(self, n, triangle):

        # Code here

Solutions:
class Solution:

	def minimizeSum(self, n, triangle):
		dp = [[-1 for j in range(n)] for i in range(n)]
		return self.cost(0, 0, n, triangle, dp)

	def cost(self, i, j, n, triangle, dp):
		if dp[i][j] != -1:
			return dp[i][j]
		if i == n - 1:
			return triangle[i][j]
		down = triangle[i][j] + self.cost(i + 1, j, n, triangle, dp)
		right = triangle[i][j] + self.cost(i + 1, j + 1, n, triangle, dp)
		dp[i][j] = min(down, right)
		return dp[i][j]


class Solution:

	def minimizeSum(self, n, triangle):
		dp = []
		for i in range(1, n + 1):
			temp = []
			for j in range(i):
				temp.append(0)
			dp.append(temp)
		dp[0][0] = triangle[0][0]
		for i in range(1, n):
			for j in range(i + 1):
				if j - 1 < 0:
					dp[i][j] = dp[i - 1][j] + triangle[i][j]
				elif j + 1 > i:
					dp[i][j] = dp[i - 1][j - 1] + triangle[i][j]
				else:
					dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j]
		return min(dp[-1])


class Solution:

	def minimizeSum(self, n, triangle):

		def func(i, j, dp):
			if i == n - 1:
				return triangle[n - 1][j]
			if dp[i][j] != -1:
				return dp[i][j]
			d = triangle[i][j] + func(i + 1, j, dp)
			dg = triangle[i][j] + func(i + 1, j + 1, dp)
			dp[i][j] = min(d, dg)
			return dp[i][j]
		dp = [[-1 for i in range(n)] for j in range(n)]
		return func(0, 0, dp)


class Solution:

	def minimizeSum(self, n, triangle):
		dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
		for i in range(n):
			for j in range(len(triangle[i])):
				dp[i][j] = -1

		def dfs(i, j):
			if i == 0 and j == 0:
				return triangle[0][0]
			if dp[i][j] != -1:
				return dp[i][j]
			if i < 0 or j >= n:
				return float('inf')
			dp[i][j] = triangle[i][j] + min(dfs(i - 1, j), dfs(i - 1, j - 1))
			return dp[i][j]
		res = float('inf')
		last = triangle[-1]
		for i in range(len(last)):
			res = min(res, dfs(n - 1, i))
		return res


class Solution:

	def minimizeSum(self, n, triangle):

		def fun(ind, i, dp):
			if ind == len(triangle):
				return 0
			if dp[ind][i] != -1:
				return dp[ind][i]
			left = triangle[ind][i] + fun(ind + 1, i, dp)
			right = triangle[ind][i] + fun(ind + 1, i + 1, dp)
			dp[ind][i] = min(left, right)
			return dp[ind][i]
		length = len(triangle[n - 1])
		dp = [[-1 for j in range(length)] for i in range(length)]
		ind = 0
		i = 0
		return fun(ind, i, dp)


class Solution:

	def minimizeSum(self, n, tr):
		for row in range(n - 2, -1, -1):
			for j in range(len(tr[row])):
				tr[row][j] = tr[row][j] + min(tr[row + 1][j], tr[row + 1][j + 1])
		return tr[0][0]


class Solution:

	def minimizeSum(self, n, triangle):
		dp = [[-1 for i in range(n + 1)] for j in range(n + 1)]
		return self.helper(0, 0, triangle, n, dp)

	def helper(self, i, j, triangle, n, dp):
		if i == n - 1:
			return triangle[i][j]
		if dp[i][j] != -1:
			return dp[i][j]
		down = triangle[i][j] + self.helper(i + 1, j, triangle, n, dp)
		diagonal = triangle[i][j] + self.helper(i + 1, j + 1, triangle, n, dp)
		dp[i][j] = min(down, diagonal)
		return dp[i][j]


class Solution:

	def minimizeSum(self, n, triangle):
		for i in range(len(triangle) - 2, -1, -1):
			for j in range(len(triangle[i])):
				triangle[i][j] = triangle[i][j] + min(triangle[i + 1][j], triangle[i + 1][j + 1])
		return triangle[0][0]


class Solution:

	def minimizeSum(self, n, t):
		dp = []
		import sys
		sys.setrecursionlimit(10 ** 9)
		for i in range(n):
			pp = [sys.maxsize] * (i + 1)
			dp.append(pp)
		return self.solve(0, 0, n, t, dp)

	def solve(self, i, j, n, t, dp):
		import sys
		if i == n - 1:
			return t[i][j]
		if dp[i][j] != sys.maxsize:
			return dp[i][j]
		down = t[i][j] + self.solve(i + 1, j, n, t, dp)
		downdiag = t[i][j] + self.solve(i + 1, j + 1, n, t, dp)
		dp[i][j] = min(dp[i][j], min(down, downdiag))
		return dp[i][j]


class Solution:

	def minimizeSum(self, n, triangle):
		prev = [-1] * n
		for i in range(n - 1, -1, -1):
			curr = [-1] * n
			for j in range(i, -1, -1):
				if i == n - 1:
					curr[j] = triangle[i][j]
				else:
					down = triangle[i][j] + prev[j]
					right = triangle[i][j] + prev[j + 1]
					curr[j] = min(down, right)
			prev = curr
		return curr[0]


class Solution:

	def minimizeSum(self, n, triangle):
		dp = [[0 for i in range(len(triangle[j]))] for j in range(len(triangle))]
		for i in range(len(triangle)):
			for j in range(len(triangle[i])):
				if i == 0 and j == 0:
					dp[0][0] = triangle[0][0]
					continue
				dp[i][j] = triangle[i][j] + min(dp[i - 1][j] if -1 < j < len(triangle[i - 1]) else float('inf'), dp[i - 1][j - 1] if -1 < j - 1 < len(triangle[i - 1]) else float('inf'))
		return min(dp[-1])


class Solution:

	def minimizeSum(self, n, triangle):
		prev = triangle[n - 1][:]
		for i in range(n - 2, -1, -1):
			curr = [0] * (i + 1)
			for j in range(i, -1, -1):
				same = triangle[i][j] + prev[j]
				diff = triangle[i][j] + prev[j + 1]
				curr[j] = min(same, diff)
			prev[:] = curr[:]
		return prev[0]


class Solution:

	def minimizeSum(self, n, triangle):
		dp = [[-1 for _ in range(i + 1)] for i in range(n)]
		for i in range(n - 1, -1, -1):
			for j in range(i, -1, -1):
				if i == n - 1:
					dp[i][j] = triangle[i][j]
					continue
				same = triangle[i][j] + dp[i + 1][j]
				diff = triangle[i][j] + dp[i + 1][j + 1]
				dp[i][j] = min(same, diff)
		return dp[0][0]


class Solution:

	def minimizeSum(self, n, triangle):
		dp = []
		import sys
		if n == 1:
			return triangle[0][0]
		for i in range(n):
			l_ = []
			for j in range(i + 1):
				l_.append(sys.maxsize)
			dp.append(l_)
		dp[0][0] = triangle[0][0]
		for i in range(n):
			for j in range(i + 1):
				if i == 0:
					continue
				up = sys.maxsize
				upd = sys.maxsize
				if j != i:
					up = dp[i - 1][j] + triangle[i][j]
				if j != 0:
					upd = dp[i - 1][j - 1] + triangle[i][j]
				dp[i][j] = min(dp[i][j], min(up, upd))
		min_ = sys.maxsize
		for j in range(n):
			min_ = min(min_, dp[n - 1][j])
		return min_

	def solve(self, i, j, n, t, dp):
		import sys
		if i == n - 1:
			return t[i][j]
		if dp[i][j] != sys.maxsize:
			return dp[i][j]
		down = t[i][j] + self.solve(i + 1, j, n, t, dp)
		downdiag = t[i][j] + self.solve(i + 1, j + 1, n, t, dp)
		dp[i][j] = min(dp[i][j], min(down, downdiag))
		return dp[i][j]


class Solution:

	def solve(self, r, c, arr, N, dp):
		if r >= N:
			return 0
		if dp[r][c] != -1:
			return dp[r][c]
		MIN = arr[r][c] + self.solve(r + 1, c, arr, N, dp)
		if c + 1 < len(arr[r]):
			MIN = min(MIN, arr[r][c + 1] + self.solve(r + 1, c + 1, arr, N, dp))
		dp[r][c] = MIN
		return MIN

	def minimizeSum(self, n, triangle):
		dp = [[-1 for _ in i] for i in triangle]
		return self.solve(0, 0, triangle, n, dp)


class Solution:
	dp = []

	def gen(self, n, triangle, row, col):
		if row > n:
			return 0
		if self.dp[row][col] != -1:
			return self.dp[row][col]
		r = 9999999999
		l = self.gen(n, triangle, row + 1, col) + triangle[row][col]
		if col + 1 <= row + 1:
			r = self.gen(n, triangle, row + 1, col + 1) + triangle[row][col]
		self.dp[row][col] = min(l, r)
		return min(l, r)

	def minimizeSum(self, n, triangle):
		self.dp = []
		for i in range(n):
			arr = []
			for j in range(n):
				arr.append(-1)
			self.dp.append(arr)
		a = self.gen(n - 1, triangle, 0, 0)
		return a


class Solution:

	def minimizeSum(self, n, triangle):
		dp = [[99999999 for i in range(n)] for j in range(n)]
		dp[0][0] = triangle[0][0]
		for i in range(n):
			for j in range(i + 1):
				if i + 1 < n:
					one = triangle[i + 1][j]
					two = triangle[i + 1][j + 1]
					if one + dp[i][j] < dp[i + 1][j]:
						dp[i + 1][j] = dp[i][j] + one
					if two + dp[i][j] < dp[i + 1][j + 1]:
						dp[i + 1][j + 1] = dp[i][j] + two
		return min(dp[n - 1])


class Solution:

	def minimizeSum(self, n, triangle):
		dp = [[float('inf')] * n for i in range(n)]
		dp[0][0] = triangle[0][0]
		for i in range(1, n):
			for j in range(i + 1):
				dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j]
		return min(dp[-1])


class Solution:

	def minimizeSum(self, n, triangle):
		l = []
		for i in range(n):
			l += [[0] * n]
		l[0][0] = triangle[0][0]
		for i in range(1, n):
			for j in range(i + 1):
				if j - 1 >= 0 and j <= i - 1:
					l[i][j] = triangle[i][j] + min(l[i - 1][j], l[i - 1][j - 1])
				elif j <= i - 1:
					l[i][j] = triangle[i][j] + l[i - 1][j]
				else:
					l[i][j] = triangle[i][j] + l[i - 1][j - 1]
		return min(l[n - 1])


class Solution:

	def minimizeSum(self, n, tri):

		def calc(r, c):
			prev = tri[-1]
			for i in range(r - 2, -1, -1):
				temp = [-1] * (i + 1)
				for j in range(i, -1, -1):
					(le, ri) = (float('inf'), float('inf'))
					if i + 1 < r:
						le = tri[i][j] + prev[j]
					if i + 1 < r and j + 1 < c:
						ri = tri[i][j] + prev[j + 1]
					temp[j] = min(le, ri)
				prev = temp
			return temp[0]
		if n == 1:
			return tri[0][0]
		return calc(len(tri), len(tri[-1]))


class Solution:

	def minimizeSum(self, n, tri):

		def calc(r, c):
			dp = [[-1 for i in range(len(tri[-1]))] for j in range(len(tri))]
			for i in range(r - 1, -1, -1):
				for j in range(i, -1, -1):
					if i == r - 1:
						dp[i][j] = tri[i][j]
					else:
						(le, ri) = (float('inf'), float('inf'))
						if i + 1 < r:
							le = tri[i][j] + dp[i + 1][j]
						if i + 1 < r and j + 1 < c:
							ri = tri[i][j] + dp[i + 1][j + 1]
						dp[i][j] = min(le, ri)
			return dp[0][0]
		return calc(len(tri), len(tri[-1]))


import collections

class Solution:

	def minimizeSum(self, n, triangle):
		l = collections.deque([[triangle[0][0], 0]])
		for i in range(1, n):
			m = len(l)
			d = {}
			for j in range(0, m):
				ele = l.popleft()
				if ele[1] not in d:
					d[ele[1]] = [ele[0] + triangle[i][ele[1]], ele[1]]
				elif ele[0] + triangle[i][ele[1]] < d[ele[1]][0]:
					d[ele[1]] = [ele[0] + triangle[i][ele[1]], ele[1]]
				if ele[1] + 1 not in d:
					d[ele[1] + 1] = [ele[0] + triangle[i][ele[1] + 1], ele[1] + 1]
				elif ele[0] + triangle[i][ele[1] + 1] < d[ele[1] + 1][0]:
					d[ele[1] + 1] = [ele[0] + triangle[i][ele[1] + 1], ele[1] + 1]
			for j in d:
				l.append(d[j])
		mi = 9999999
		for i in l:
			if i[0] < mi:
				mi = i[0]
		return mi


class Solution:

	def solve(self, row, col, grid, dp):
		n = len(grid)
		if row == n - 1:
			return grid[row][col]
		if dp[row][col] != -1:
			return dp[row][col]
		up = grid[row][col] + self.solve(row + 1, col, grid, dp)
		rightDiag = grid[row][col] + self.solve(row + 1, col + 1, grid, dp)
		dp[row][col] = min(up, rightDiag)
		return dp[row][col]

	def minimizeSum(self, n, grid):
		dp = [[-1 for j in range(n)] for i in range(n)]
		res = self.solve(0, 0, grid, dp)
		return res


class Solution:

	def minimizeSum(self, n, triangle):

		def helper(i, j):
			if i == n - 1:
				return triangle[i][j]
			if dp[i + 1][j] == -1:
				ans1 = helper(i + 1, j)
				dp[i + 1][j] = ans1
			else:
				ans1 = dp[i + 1][j]
			if dp[i + 1][j + 1] == -1:
				ans2 = helper(i + 1, j + 1)
				dp[i + 1][j + 1] = ans2
			else:
				ans2 = dp[i + 1][j + 1]
			return triangle[i][j] + min(ans1, ans2)
		dp = [[-1 for i in range(j + 1)] for j in range(n)]
		return helper(0, 0)


class Solution:

	def fun(self, i, j, n, arr, dp):
		if i == n - 1:
			return arr[n - 1][j]
		if dp[i][j] != -1:
			return dp[i][j]
		up = arr[i][j] + self.fun(i + 1, j, n, arr, dp)
		diagonal = arr[i][j] + self.fun(i + 1, j + 1, n, arr, dp)
		dp[i][j] = min(up, diagonal)
		return dp[i][j]

	def minimizeSum(self, n, triangle):
		dp = [[0 for i in range(n)] for j in range(n)]
		for j in range(n):
			dp[n - 1][j] = triangle[n - 1][j]
		for i in range(n - 2, -1, -1):
			for j in range(i, -1, -1):
				down = triangle[i][j] + dp[i + 1][j]
				diagonal = triangle[i][j] + dp[i + 1][j + 1]
				dp[i][j] = min(down, diagonal)
		return dp[0][0]


class Solution:

	def minimizeSum(self, n, arr):
		dp = [[10000000000.0 for i in range(n)] for j in range(n)]
		dp[0][0] = arr[0][0]
		for i in range(1, n):
			dp[i][0] = dp[i - 1][0] + arr[i][0]
			for j in range(1, len(arr[i]) - 1):
				dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + arr[i][j]
			dp[i][len(arr[i]) - 1] = dp[i - 1][len(arr[i]) - 2] + arr[i][-1]
		return min(dp[n - 1])


class Solution:

	def minimizeSum(self, n, t):
		dp = [[0 for i in range(n)] for i in range(n)]
		for i in range(n):
			for j in range(len(t[i])):
				if i == 0:
					dp[i][j] = t[i][j]
					continue
				if j == 0:
					dp[i][j] = dp[i - 1][j] + t[i][j]
				elif j == len(t[i]) - 1:
					dp[i][j] = dp[i - 1][j - 1] + t[i][j]
				else:
					dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + t[i][j]
		return min(dp[-1])


class Solution:

	def f(self, i, j, n, triangle, dp):
		if i == n - 1:
			return triangle[n - 1][j]
		if i < 0 or j < 0:
			return 1000000000.0
		if dp[i][j] != -1:
			return dp[i][j]
		minn = 1000000000.0
		down = triangle[i][j] + self.f(i + 1, j, n, triangle, dp)
		dia = triangle[i][j] + self.f(i + 1, j + 1, n, triangle, dp)
		minn = min(down, dia)
		dp[i][j] = minn
		return dp[i][j]

	def minimizeSum(self, n, triangle):
		dp = [[-1 for i in range(n - 1)] for j in range(len(triangle[n - 1]))]
		return self.f(0, 0, n, triangle, dp)


class Solution:

	def minimizeSum(self, n, triangle):
		prev = [0] * n
		for j in range(n):
			prev[j] = triangle[n - 1][j]
		for i in range(n - 2, -1, -1):
			curr = [0] * n
			for j in range(i, -1, -1):
				down = 0
				diag = 0
				down += triangle[i][j] + prev[j]
				diag += triangle[i][j] + prev[j + 1]
				curr[j] = min(down, diag)
			prev = curr
		return prev[0]


class Solution:

	def minimizeSum(self, n, triangle):
		prev = [0] * n
		for col in range(n):
			prev[col] = triangle[n - 1][col]
		for row in range(n - 2, -1, -1):
			curr = [0] * n
			for col in range(row, -1, -1):
				Down = triangle[row][col] + prev[col]
				Diag = triangle[row][col] + prev[col + 1]
				curr[col] = min(Down, Diag)
			prev = curr
		return prev[0]


class Solution:

	def minimizeSum(self, n, triangle):
		dp = [[-1] * n for i in range(n)]
		for col in range(n - 1, -1, -1):
			dp[n - 1][col] = triangle[n - 1][col]
		for row in range(n - 2, -1, -1):
			for col in range(row, -1, -1):
				Down = triangle[row][col] + dp[row + 1][col]
				Diag = triangle[row][col] + dp[row + 1][col + 1]
				dp[row][col] = min(Down, Diag)
		return dp[0][0]


class Solution:

	def minimizeSum(self, n, triangle):
		dp = [[-1 for i in range(n)] for i in range(n)]

		def recursive(triangle, n, idx=0, cl=0):
			nonlocal dp
			if idx == n:
				return 0
			if cl >= len(triangle[idx]) or idx >= n:
				return float('inf')
			if dp[idx][cl] != -1:
				return dp[idx][cl]
			dp[idx][cl] = triangle[idx][cl] + min(recursive(triangle, n, idx + 1, cl), recursive(triangle, n, idx + 1, cl + 1))
			return dp[idx][cl]
		return recursive(triangle, n)


class Solution:

	def minimizeSum(self, n, triangle):
		prev = [triangle[0][0]]
		for i in range(1, n):
			prev.append(prev[-1] + triangle[i][0])
		mini = prev[-1]
		for j in range(1, n):
			temp = []
			for i in range(j, n):
				if j == i:
					temp.append(triangle[i][j] + prev[0])
				else:
					temp.append(min(triangle[i][j] + prev[len(temp)], triangle[i][j] + temp[-1]))
			mini = min(mini, temp[-1])
			prev = temp
		return mini


class Solution:

	def minimizeSum(self, n, triangle):
		ahead = [0] * n
		for j in range(0, n):
			ahead[j] = triangle[n - 1][j]
		for i in range(n - 2, -1, -1):
			curr = [0] * n
			for j in range(i, -1, -1):
				down = triangle[i][j] + ahead[j]
				down_right = triangle[i][j] + ahead[j + 1]
				curr[j] = min(down, down_right)
			ahead = curr
		return ahead[0]


class Solution:

	def solvememo(self, triangle, i, j, n, dp):
		if i == n - 1:
			return triangle[i][j]
		if dp[i][j] != -1:
			return dp[i][j]
		down = triangle[i][j] + self.solvememo(triangle, i + 1, j, n, dp)
		diagonal = triangle[i][j] + self.solvememo(triangle, i + 1, j + 1, n, dp)
		dp[i][j] = min(down, diagonal)
		return dp[i][j]

	def solveTab(self, triangle, i, j, n):
		dp = [[0] * n for i in range(n)]
		for j in range(n):
			dp[n - 1][j] = triangle[n - 1][j]
		for i in range(n - 2, -1, -1):
			for j in range(i, -1, -1):
				down = triangle[i][j] + dp[i + 1][j]
				diagonal = triangle[i][j] + dp[i + 1][j + 1]
				dp[i][j] = min(down, diagonal)
		return dp[0][0]

	def solveOpt(self, triangle, i, j, n):
		front = [0] * n
		for j in range(n):
			front[j] = triangle[n - 1][j]
		for i in range(n - 2, -1, -1):
			cur = [0] * n
			for j in range(i, -1, -1):
				down = triangle[i][j] + front[j]
				diagonal = triangle[i][j] + front[j + 1]
				cur[j] = min(down, diagonal)
			front = cur
		return front[0]

	def minimizeSum(self, n, triangle):
		return self.solveOpt(triangle, 0, 0, n)


class Solution:

	def minimizeSum(self, n, triangle):

		def recur(row, col):
			if row == n - 1:
				return triangle[row][col]
			if col >= n:
				return 1000000000.0
			if dp[row][col] != -1:
				return dp[row][col]
			down = triangle[row][col] + recur(row + 1, col)
			right = triangle[row][col] + recur(row + 1, col + 1)
			dp[row][col] = min(down, right)
			return dp[row][col]
		dp = [[-1] * n for _ in range(n)]
		return recur(0, 0)


class Solution:

	def __init__(self):
		self.dp = dict()

	def minimizeSum(self, n, triangle, index=0, l=0):
		if l == n:
			return 0
		if self.dp.get((l, index)) != None:
			return self.dp[l, index]
		if l == 0:
			return triangle[0][0] + self.minimizeSum(n, triangle[1:], 0, l + 1)
		w1 = triangle[0][index] + self.minimizeSum(n, triangle[1:], index, l + 1)
		w2 = triangle[0][index + 1] + self.minimizeSum(n, triangle[1:], index + 1, l + 1)
		self.dp[l, index] = min(w1, w2)
		return self.dp[l, index]


class Solution:

	def minimizeSum(self, n, triangle):
		dp = [[-1 for i in range(len(triangle[-1]))] for i in range(len(triangle))]

		def func(i, j, triangle, dp):
			if i == len(triangle) - 1:
				return triangle[i][j]
			if dp[i][j] != -1:
				return dp[i][j]
			down = triangle[i][j] + func(i + 1, j, triangle, dp)
			diag = triangle[i][j] + func(i + 1, j + 1, triangle, dp)
			dp[i][j] = min(down, diag)
			return dp[i][j]
		return func(0, 0, triangle, dp)


class Solution:

	def minimizeSum(self, n, triangle):
		first = [0 for i in range(n)]
		for i in range(n):
			first[i] = triangle[n - 1][i]
		cur = [0 for i in range(n)]
		for i in range(n - 2, -1, -1):
			for j in range(i, -1, -1):
				d = first[j] + triangle[i][j]
				d_ = first[j + 1] + triangle[i][j]
				cur[j] = min(d, d_)
			first = cur[:]
		return first[0]


class Solution:

	def minimizeSum(self, n, triangle):

		def path(i, j):
			if i == 0 and j == 0:
				return triangle[i][j]
			if j < 0 or i < 0:
				return float('inf')
			if dp[i][j] != -1:
				return dp[i][j]
			l = float('inf')
			r = float('inf')
			if j < len(triangle[i]):
				l = path(i - 1, j - 1) + triangle[i][j]
			if j < len(triangle[i]):
				r = path(i - 1, j) + triangle[i][j]
			dp[i][j] = min(l, r)
			return dp[i][j]
		prev = [float('inf')] * n
		prev[0] = triangle[0][0]
		for i in range(1, n):
			curr = [float('inf')] * n
			for j in range(len(triangle[i])):
				l = float('inf')
				r = float('inf')
				if j > 0 and i > 0:
					l = prev[j - 1] + triangle[i][j]
				if i > 0:
					r = prev[j] + triangle[i][j]
				curr[j] = min(l, r)
			prev = curr
		return min(prev)


mod = 10 ** 9 + 7

class Solution:

	def minimizeSum(self, n, grid):

		def helper(row, col):
			if row == n - 1:
				return grid[row][col]
			if dp[row][col] != -1:
				return dp[row][col]
			down = grid[row][col] + helper(row + 1, col)
			diag = grid[row][col] + helper(row + 1, col + 1)
			dp[row][col] = min(down, diag)
			return dp[row][col]
		dp = [[-1 for _ in range(n)] for _ in range(n)]
		return helper(0, 0)


class Solution:

	def minimizeSum(self, n, triangle):
		dp = [[0] * n for _ in range(n)]
		for j in range(0, n):
			dp[n - 1][j] = triangle[n - 1][j]
		for i in range(n - 2, -1, -1):
			for j in range(i, -1, -1):
				d = triangle[i][j] + dp[i + 1][j]
				dg = triangle[i][j] + dp[i + 1][j + 1]
				dp[i][j] = min(d, dg)
		return dp[0][0]


class Solution:

	def minimizeSum(self, n, triangle):
		n = len(triangle)
		dp = [0] * n
		for j in range(n):
			dp[j] = triangle[n - 1][j]
		for i in range(n - 2, -1, -1):
			cur = [0] * n
			for j in range(i, -1, -1):
				down = triangle[i][j] + dp[j]
				diag = triangle[i][j] + dp[j + 1]
				cur[j] = min(down, diag)
			dp = cur
		return dp[0]


class Solution:

	def minimizeSum(self, n, triangle):
		dp = [[-1 for i in range(n)] for j in range(n)]
		for j in range(n):
			dp[n - 1][j] = triangle[n - 1][j]
		for i in range(n - 2, -1, -1):
			for j in range(i, -1, -1):
				down = triangle[i][j] + dp[i + 1][j]
				digonal = triangle[i][j] + dp[i + 1][j + 1]
				dp[i][j] = min(down, digonal)
		return dp[0][0]


class Solution:

	def minimizeSum(self, n, arr):
		prev = []
		for j in range(0, n):
			prev.append(arr[n - 1][j])
		colsize = n - 1
		for i in range(n - 2, -1, -1):
			temp = [0] * colsize
			for j in range(0, colsize):
				temp[j] = arr[i][j] + min(prev[j], prev[j + 1])
			colsize -= 1
			prev = temp
		return prev[0]


class Solution:

	def minimizeSum(self, n, arr):
		dp = []
		for i in range(0, n):
			m = len(arr[i])
			temp = [-1] * m
			if i == n - 1:
				dp.append(arr[i])
			else:
				dp.append(temp)
		colsize = n - 1
		for i in range(n - 2, -1, -1):
			for j in range(0, colsize):
				dp[i][j] = arr[i][j] + min(dp[i + 1][j], dp[i + 1][j + 1])
			colsize -= 1
		return dp[0][0]


class Solution:

	def minimizeSum(self, n, arr):

		def solve(i, j):
			if i == n - 1:
				return arr[i][j]
			if dp[i][j] != -1:
				return dp[i][j]
			dp[i][j] = arr[i][j] + min(solve(i + 1, j), solve(i + 1, j + 1))
			return dp[i][j]
		dp = []
		for i in range(0, n):
			m = len(arr[i])
			temp = [-1] * m
			dp.append(temp)
		return solve(0, 0)


class Solution:

	def minimizeSum(self, m, triangle):
		if len(triangle) == 1:
			return triangle[0][0]
		m = len(triangle)
		dp = [[float('inf') for i in range(m)] for i in range(m)]
		dp[0][0] = triangle[0][0]
		for i in range(1, m):
			for j in range(len(triangle[i])):
				dir = [0, -1]
				temp = 10 ** 9
				for y in dir:
					if j + y >= 0:
						dum = triangle[i][j] + dp[i - 1][j + y]
						temp = min(temp, dum)
				dp[i][j] = temp
		return min(dp[-1])


class Solution:

	def minimizeSum(self, m, triangle):
		le = len(triangle[m - 1])
		dp = [[-1 for i in range(le)] for i in range(m)]

		def minpath(m, n, l, triangle):
			if dp[m][n] != -1:
				return dp[m][n]
			if m == len(triangle) - 1:
				return triangle[m][n]
			down = triangle[m][n] + minpath(m + 1, n, l + 1, triangle)
			diagonal = triangle[m][n] + minpath(m + 1, n + 1, l + 1, triangle)
			dp[m][n] = min(down, diagonal)
			return dp[m][n]
		return minpath(0, 0, 0, triangle)


class Solution:

	def minimizeSum(self, n, triangle):
		m = n + 1
		dp = []
		for i in range(m):
			dp.append([0] * m)
		for i in range(n - 1, -1, -1):
			for j in range(i + 1):
				dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]
		return dp[0][0]