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

DP на интервалах: как это работает?

Состояние это пара, два конца отрезка. Оно хранит лучший результат внутри этих границ.

Идите по длине отрезка, от коротких к длинным. Всё, что вы читаете, уже посчитано.

Для одного отрезка переберите все точки разреза внутри. Каждый разрез даёт одного кандидата.

Кандидат складывает левую часть, правую и стоимость их соединения. Оставляйте лучшего из них.

Вся задача сидит именно в стоимости соединения. В шариках она зависит от двух границ.

Ответ это состояние, накрывающее весь вход. Оно заполняется самым последним.

1. с полями: [1, 3, 1, 5, 1]Лопаем шарики. По краям добавлена единица, она не лопается.
2. отрезки ширины один: 0Внутри них лопать нечего.
3. dp(1, 3) = 15Единица между 3 и 5 даёт 3 умножить на 1 и на 5.
4. dp(0, 3) = 30Тройку лопаем последней, поэтому она стоит 1 на 3 на 5.
5. dp(0, 4) = 35Пятёрка идёт последней. Все короткие отрезки уже готовы.

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];
}

DP на интервалах: разбор примера

Наибольшая палиндромная подпоследовательность

Верните длину наибольшей палиндромной подпоследовательности строки.

Буквы не обязаны стоять рядом друг с другом.

Состоянием служит отрезок строки.

Если концы совпали, они добавляют двойку к внутреннему отрезку. Иначе отбросьте один конец и возьмите лучшее.

function longestPalindromeSubseq(s) {
    const n = s.length;
    const dp = Array.from({ length: n }, () => new Array(n).fill(0));

    // i walks backwards so every inner range is already filled
    for (let i = n - 1; i >= 0; i--) {
        dp[i][i] = 1; // a single letter is a palindrome

        for (let j = i + 1; j < n; j++) {
            if (s[i] === s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[0][n - 1];
}

DP на интервалах: когда применять?

Эти формулировки в условии ведут сюда:

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

DP на интервалах: с чем путают?

• Динамическое программирование (1-D) (Dynamic programming (1-D)): Один индекс описывает префикс. Отрезку нужны оба конца.
• DP над подпоследовательностями (LIS / LCS / расстояние редактирования) (DP on subsequences (LIS / LCS / edit distance)): Там два индекса указывают в две разные последовательности. Здесь оба лежат в одной.
• DP на деревьях (DP on trees): Дерево делится по своим потомкам, и они заданы. Отрезок делится в точке, которую вы выбираете.
• Жадный алгоритм (обменный аргумент) (Greedy (exchange argument)): Жадность выбрала бы порядок и на нём остановилась. Здесь надо перебрать все точки разреза.

DP на интервалах: частые ошибки

• Гоняют i и j как в обычной сетке

  Отрезок заполняется после всего, что внутри него. Идите по длине или ведите i назад.

• Выбирают первый ход вместо последнего

  В шариках фиксированных соседей имеет только последний лопнувший. Выбор первого делает состояние неверным.

• Забывают про поля по краям

  Нейтральное значение с каждой стороны убирает крайние случаи. Без него границы требуют отдельного кода.

• Запускают это на большом входе

  O(n в кубе) умирает после нескольких тысяч элементов. Проверьте n до написания трёх циклов.

DP на интервалах: задачи с собеседований

• Лопающиеся шарики: Выбирается шарик, который лопнет последним.
• Наибольшая палиндромная подпоследовательность: Концы совпали или один из них отброшен.
• Минимальная триангуляция многоугольника: Каждая точка разреза даёт треугольник.
• Странный принтер: Одна печать накрывает целый отрезок.
• Удаление коробок: Состояние несёт ещё и счётчик рядом с отрезком.
• Число палиндромных подстрок: Считается каждый отрезок, который является палиндромом.
• Минимальная стоимость слияния камней: Деление идёт на группы по k, а не надвое.

DP на интервалах: сложность по времени и памяти

O(n^3)

n примерно до 500 даёт O(n в кубе). Отрезков n в квадрате, и у каждого n точек разреза.