В этой задаче Leetcode нам дан многоугольник, в котором каждая вершина (узел) имеет значение. Значение треугольника - это произведение всех значений его вершин. Мы должны разделить его на треугольники, чтобы сумма всех значений треугольников была минимальной.
Мы можем решить эту проблему жадным способом разделяй и властвуй, заметив, что, выбирая 3 минимальных значения и делая из них треугольник, мы делим многоугольник на 3 новых многоугольника.
Подход довольно прост, но детали кодирования могут быть не так просты в управлении из-за ограничений границ и манипуляций с массивом или индексом в массиве. Вот мой код решения:
func minScoreTriangulation(A []int) int {
if len(A) < 3 {
return 0
}
if len(A) == 3 {
return A[0] * A[1] * A[2]
}
var min [3]int
var ind [3]int
min[0] = 101
min[1] = 101
min[2] = 101
maxIndex := 0
for i, v := range A {
if v < min[maxIndex] {
min[maxIndex] = v
ind[maxIndex] = i
maxIndex = findMaxIndex(min)
}
}
a := findMinIndex(ind)
c := findMaxIndex(ind)
b := findMiddleIndex(a, c)
score := min[0] * min[1] * min[2] + minScoreTriangulation(A[ind[a]:ind[b]+1]) + minScoreTriangulation(A[ind[b]:ind[c]+1])
tmp := make([]int, 0)
tmp = append(tmp, A[ind[c]:len(A)]...)
tmp = append(tmp, A[0:ind[a]+1]...)
score += minScoreTriangulation(tmp)
return score
}
func findMaxIndex(A [3]int) int {
max := A[0]
maxIndex := 0
for i, v := range A {
if v > max {
max = v
maxIndex = i
}
}
return maxIndex
}
func findMinIndex(A [3]int) int {
min := A[0]
minIndex := 0
for i, v := range A {
if v < min {
min = v
minIndex = i
}
}
return minIndex
}
func findMiddleIndex(minIndex int, maxIndex int) int {
for i := 0; i < 3 ; i++ {
if i != minIndex && i != maxIndex {
return i
}
}
return -1
}
Bonus question: Что бы произошло, если бы каждому потенциальному ребру (i, j) (неориентированному) было присвоено значение v(i,j) вместо вершин? Значение треугольника (i, j, k) станет v(i,j) * v(j,k) * v(i,k). Как же тогда мы сможем найти лучшую триангуляцию? Будет ли работать жадный подход? При каких условиях?
