Сложность: medium
У вас есть выпуклый n-сторонний многоугольник, каждая вершина которого имеет целочисленное значение. Вам дан целочисленный массив values, где values[i] - это значение i-й вершины (т.е. по часовой стрелке). Вы должны триангулировать многоугольник на n - 2 треугольника. Для каждого треугольника значение этого треугольника равно произведению значений его вершин, а общий балл триангуляции равен сумме этих значений для всех n - 2 треугольников в триангуляции. Верните наименьший возможный общий балл, который вы можете получить с помощью некоторой триангуляции многоугольника.
Пример:
Input: values = [1,2,3]
Output: 6
👨💻 Алгоритм:
1⃣Инициализация:
Создаем двумерный массив dp, где dp[i][j] будет хранить минимальный возможный общий балл триангуляции многоугольника, состоящего из вершин от i до j.
2⃣Основное заполнение dp:
Проходим по всем возможным длинам подмногоугольников, начиная с треугольников (длина 3) до всего многоугольника (длина n).
Для каждого подмногоугольника находим минимальный возможный общий балл, проверяя все возможные треугольники, которые могут быть образованы из этого подмногоугольника.
Заполнение dp для каждого подмногоугольника:
Для каждого подмногоугольника от i до j, и для каждой возможной вершины k между i и j, обновляем значение dp[i][j], как сумму минимальных значений триангуляций левой и правой частей подмногоугольника, а также значения текущего треугольника, образованного вершинами i, k и j.
3⃣Возврат результата:
Ответ будет в dp[0][n-1], который хранит минимальный возможный общий балл триангуляции для всего многоугольника.
😎 Решение:
function minScoreTriangulation($values) {
$n = count($values);
$dp = array_fill(0, $n, array_fill(0, $n, 0));
for ($length = 2; $length < $n; $length++) {
for ($i = 0; $i < $n - $length; $i++) {
$j = $i + $length;
$dp[$i][$j] = PHP_INT_MAX;
for ($k = $i + 1; $k < $j; $k++) {
$dp[$i][$j] = min($dp[$i][$j], $dp[$i][$k] + $dp[$k][$j] + $values[$i] * $values[$j] * $values[$k]);
}
}
}
return $dp[0][$n - 1];
}Ставь 👍 и забирай 📚 Базу знаний