Оптимальная триангуляция выпуклого многоугольника через interval DP — как считать минимальный периметр?

Да, это interval DP с той же структурой, что и матрицы. Трюк — отрезок [i..j] = подмногоугольник на вершинах от i до j плюс ребро (i, j). Мы перебираем третью вершину k треугольника, опирающегося на ребро (i, j):

dp[i][j] = минимальная стоимость триангуляции подмногоугольника i, i+1, ..., j (где (i,j) — фиксированное ребро/диагональ-основание).

int n;
double x[1005], y[1005];
auto d = [&](int a, int b) {
  return hypot(x[a] - x[b], y[a] - y[b]);
};
vector<vector<double>> dp(n, vector<double>(n, 0));

for (int len = 2; len < n; ++len)        // расстояние между i и j
  for (int i = 0; i + len < n; ++i) {
    int j = i + len;
    dp[i][j] = 1e18;
    for (int k = i + 1; k < j; ++k) {
      double cost = dp[i][k] + dp[k][j]
                  + d(i, k) + d(k, j) + d(i, j); // периметр треуг.
      dp[i][j] = min(dp[i][j], cost);
    }
  }
// ответ dp[0][n-1]

Если минимизируешь только сумму диагоналей (а не периметр), не добавляй стороны самого многоугольника — добавляй лишь те рёбра треугольника, которые являются диагоналями. Сложность $O(n^3)$ времени, $O(n^2)$ памяти.