Почему мой interval DP даёт неверный ответ — порядок заполнения по длине отрезка важнее, чем кажется?

Почти наверняка проблема в порядке заполнения. В interval DP dp[i][j] зависит от более коротких отрезков (dp[i][k] и dp[k+1][j], оба короче [i,j]). Если ты идёшь циклами for i (возр.) for j (возр.), то к моменту вычисления dp[i][j] отрезок dp[k+1][j] при k+1 > i может быть ещё не посчитан — берёшь мусор.

Правильно — внешний цикл по длине отрезка, чтобы гарантировать: все короткие отрезки готовы до длинных:

for (int len = 2; len <= n; ++len)        // сначала короткие, потом длинные
  for (int i = 0; i + len - 1 < n; ++i) {
    int j = i + len - 1;
    dp[i][j] = INF;
    for (int k = i; k < j; ++k)
      dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + cost(i, j));
  }

Альтернатива — заполнять i по убыванию, j по возрастанию:

for (int i = n - 1; i >= 0; --i)
  for (int j = i; j < n; ++j)
    /* dp[i][k] (j меньше) и dp[k+1][j] (i больше) уже готовы */

Здесь при убывающем i отрезки с большим левым концом (а значит короче слева) посчитаны раньше. Оба варианта корректны; ошибка — именно наивный for i++ for j++. Сложность не меняется: $O(n^3)$.