DP на интервалах

O(n^3)

dp[i][j] хранит минимальную стоимость полного объединения отрезка [i..j]. Заполняйте по возрастанию длины отрезка, перебирая каждую точку разреза k внутри отрезка, чтобы обе половины уже были решены.

Сигналы

объединить соседние части с некоторой стоимостьюлучший способ разбить отрезок на две частипорядок перемножения цепочки матрицстоимость слияния зависит от всего отрезкаоптимальная расстановка скобок или порядок построения

Шаблон

function minMergeCost(sizes) {
    const n = sizes.length;
    const prefix = [0];
    for (const s of sizes) prefix.push(prefix[prefix.length - 1] + s);
    const dp = Array.from({ length: n }, () => new Array(n).fill(0));
    for (let len = 2; len <= n; len++) {
        for (let i = 0; i + len - 1 < n; i++) {
            const j = i + len - 1;
            dp[i][j] = Infinity;
            for (let k = i; k < j; k++) {
                const cost = dp[i][k] + dp[k + 1][j] + (prefix[j + 1] - prefix[i]);
                dp[i][j] = Math.min(dp[i][j], cost);
            }
        }
    }
    return dp[0][n - 1];
}

Похоже, но не то

Динамическое программирование (1-D): Обычное 1-D dp[i] смотрит назад лишь на один-два предыдущих индекса. Интервальное DP заполняет dp[i][j] для каждого отрезка и перебирает каждую точку РАЗРЕЗА k внутри него, потому что стоимость объединения [i..j] зависит от того, где сделан разрез, а не от фиксированного предыдущего индекса.

n до ~300..500 сегментов, перебор каждой точки разреза для каждого отрезка -> O(n^3): O(n^2) отрезков умножить на O(n) вариантов разреза.

Изучить этот паттерн