1679
правок
Изменения
м
Нет описания правки
<tex> D[i][j] = \min\limits_{k = i}^{j - 1} \left ( D[i][k] + D[k + 1][j] \right ) + \sum\limits_{t = i}^{j} f_t </tex>
Базой динамики будет <tex> D[i][i] = 0 </tex>
Добавочный член <tex> \sum\limits_{t = i}^{j} f_t </tex> возникает от того что каждым объединением двух подотрезков мы увеличиваем высоту дерева на 1, а значит, и длины всех кодов символов <tex> c_i .. c_j </tex> также увеличиваются на 1.
Тогда такое ''наибольшее'' k, на котором достигается этот минимум, называется точкой разреза для отрезка <tex> [i, j] </tex>. Пусть в ячейке <tex> R[i][j] </tex> хранится точка разреза на отрезке <tex> [i, j] </tex>.
== Монотонность точки разреза ==
