Редактирование: Динамическое программирование

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 53: Строка 53:
 
=== Принцип оптимальности на подотрезках===
 
=== Принцип оптимальности на подотрезках===
 
Требуется посчитать функцию $f(1, n)$. Принцип состоит в следующем: пусть для всех отрезков $i$, $j$ (где <tex> u \leqslant i \leqslant j \leqslant v </tex>) известен оптимальный ответ для функции $f(i, j)$. Тогда мы будем вычислять $f(u, v)$ через такие $f(i, j)$. В качестве примера рассмотрим следующую классическую задачу: дана строка длины n, нужно найти максимальный подпалиндром (подпоследовательность максимальной длины, которая является палиндромом). Пусть $d(i, j)$ - ответ на задачу для подстроки, начинающаяся с символа $i$ и заканчивающаяся в символе $j$. Ясно, что $d(i, j) = 0$ для всех $i, j,$ таких что $i > j$ и $d(i, i) = 1$ для всех $i$. Пусть нам нужно посчитать значение для $d(i, j)$, причем значение $d$ для всех $l, r$, таких что <tex> i \leqslant l \leqslant r \leqslant j </tex> уже посчитаны и они оптимальны. Рассмотрим два случая: <br />
 
Требуется посчитать функцию $f(1, n)$. Принцип состоит в следующем: пусть для всех отрезков $i$, $j$ (где <tex> u \leqslant i \leqslant j \leqslant v </tex>) известен оптимальный ответ для функции $f(i, j)$. Тогда мы будем вычислять $f(u, v)$ через такие $f(i, j)$. В качестве примера рассмотрим следующую классическую задачу: дана строка длины n, нужно найти максимальный подпалиндром (подпоследовательность максимальной длины, которая является палиндромом). Пусть $d(i, j)$ - ответ на задачу для подстроки, начинающаяся с символа $i$ и заканчивающаяся в символе $j$. Ясно, что $d(i, j) = 0$ для всех $i, j,$ таких что $i > j$ и $d(i, i) = 1$ для всех $i$. Пусть нам нужно посчитать значение для $d(i, j)$, причем значение $d$ для всех $l, r$, таких что <tex> i \leqslant l \leqslant r \leqslant j </tex> уже посчитаны и они оптимальны. Рассмотрим два случая: <br />
# <tex> s(i) \neq s(j) </tex>, тогда <tex> d(i, j) = \max(d(i, j - 1), d(i + 1, j)) </tex> <br />
+
# <tex> s(i) \neq s(j), тогда d(i, j) = \max(d(i, j - 1), d(i + 1, j)) </tex> <br />
# <tex> s(i) = s(j) </tex>, тогда <tex> d(i, j) = d(i + 1, j - 1) + 2 </tex> <br />
+
# <tex> s(i) = s(j), тогда d(i, j) = d(i + 1, j - 1) + 2 </tex> <br />
 
Доказательство:<br />
 
Доказательство:<br />
 
# Так <tex>s(i) \neq s(j)</tex>, символы  $s(i)$ и $s(j)$ не могут входить в максимальный подпалиндром одновременно, то есть либо $s(i)$ входят в максимальный подпалиндром(тогда его длина $d[i, j - 1]$), либо $s(j)$ входит в максимальный подпалиндром (тогда его длина $d[i + 1, j]$), либо оба не входят в максимальный подпалиндром (тогда его длина $= d[i, j - 1] = d[i + 1, j]$). <br />
 
# Так <tex>s(i) \neq s(j)</tex>, символы  $s(i)$ и $s(j)$ не могут входить в максимальный подпалиндром одновременно, то есть либо $s(i)$ входят в максимальный подпалиндром(тогда его длина $d[i, j - 1]$), либо $s(j)$ входит в максимальный подпалиндром (тогда его длина $d[i + 1, j]$), либо оба не входят в максимальный подпалиндром (тогда его длина $= d[i, j - 1] = d[i + 1, j]$). <br />

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: