package main

func minimumTotal(triangle [][]int) int {
	length := len(triangle)
	if length == 0 {
		return 0
	}
	sum := make([]int, length)
	sum[0] = triangle[0][0]
	for i := 1; i < length; i++ { // Something like Dijkstra
		// sum[] stores all minimum which take diff index as endpoint
		former := sum[0]
		sum[0] = former + triangle[i][0]
		for j := 1; j < i; j++ {
			tmp := sum[j]
			if former < tmp {
				sum[j] = former + triangle[i][j]
			} else {
				sum[j] = tmp + triangle[i][j]
			}
			former = tmp
		}
		sum[i] = former + triangle[i][i]
	}
	min := sum[0]
	for i := 1; i < length; i++ {
		if sum[i] < min {
			min = sum[i]
		}
	}
	return min
}

// func main() {
// 	tri1 := [][]int{
// 		{2},
// 		{3, 4},
// 		{6, 5, 7},
// 		{4, 1, 8, 3}}
// 	println(minimumTotal(tri1))
// 	tri2 := [][]int{}
// 	println(minimumTotal(tri2))
// 	tri3 := [][]int{
// 		{9}}
// 	println(minimumTotal(tri3))
// }