leetcode: 120. Triangle

Difficulty

Medium.

Problem

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.

AC

class Solution():
	def minimumTotal(self, x):
		if not x:
			return 0
		way = [0] * len(x)
		way[0] = x[0][0]
		for i in range(1, len(x)):
			for j in range(len(x[i])-1, -1, -1):
				if j == len(x[i]) - 1:
					way[j] = way[j-1] + x[i][j]
				elif j == 0:
					way[j] = way[j] + x[i][j]
				else:
					way[j] = min(way[j-1], way[j]) + x[i][j]
		return min(way)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券