🌵120. Triangle
https://leetcode.com/problems/triangle/
js
/**
* @param {number[][]} triangle
* @return {number}
*/
function minimumTotal(triangle) {
let prev = []
let result = triangle[0]
for (let i = 1; i < triangle.length; i++) {
prev = result
result = []
const row = triangle[i]
for (let j = 0; j < i + 1; j++) {
if (j === 0 || (j < i && prev[j - 1] > prev[j])) {
result.push(prev[j] + row[j])
} else {
result.push(prev[j - 1] + row[j])
}
}
}
return Math.min(...result)
}py
class Solution(object):
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
prev, result = [], triangle[0]
for i in range(1, len(triangle)):
prev, result = result, []
row = triangle[i]
for j in range(i + 1):
if j == 0 or (j < i and prev[j - 1] > prev[j]):
result.append(prev[j] + row[j])
else:
result.append(prev[j - 1] + row[j])
return min(result)go
func minimumTotal(triangle [][]int) int {
prev := []int{}
result := triangle[0]
for i := 1; i < len(triangle); i++ {
prev = result
result = []int{}
row := triangle[i]
for j := 0; j <= i; j++ {
if j == 0 || (j < i && prev[j-1] > prev[j]) {
result = append(result, prev[j]+row[j])
} else {
result = append(result, prev[j-1]+row[j])
}
}
}
min := result[0]
for _, val := range result {
if val < min {
min = val
}
}
return min
}