Занятие №8. Динамическое программирование с двумя и более параметрами

Теория: Лекция                                       [Все занятия]

Практика:                                            [Официальная страница]

Учебные задачи:
   Задача A.
   [Наибольшая общая подпоследовательность (НОП)]
В данной задаче можно применить классический алгоритм Нудельмана-Вунша.
   Задача B.
   [Наибольшая общая подпоследовательность с восстановлением ответа]
Продолжение предыдущей задачи с той разницей, что в текущей реализации использовались барьерные первый столбец и строка.
   Задача C.
   [Биномиальные коэффициенты]
Наверное последняя проходная задача на ДП в этом цикле. Суть задачи сводиться к классической черепашке. 
Олимпиадные задачи:
  Задача A.
   [Движение по полосам] 
Очень хорошая задача. Решаем ДП с двумя параметрами: количество использованных полос(s), количество использованных дорог(r). Ответом на вопрос будет являться значение dp(n,m), где n – общее количество полос, m – общее количество дорог. Чтобы найти значение на текущем шаге dp(s,r), необходимо перебрать и сложить все возможные значения dp(s-1,r’).
   Задача B.
   [Еловая аллея] 
Данная реализация отражает идею, предложенную в разборе, но имеет сложность M*M*N.
   Задача C.
   [Почти палиндром]
Классическая LR динамика. Нужно быть осторожным в выборе типа данных для элементов таблицы. 
Дополнительные олимпиадные задачи:
  Задача A.
   [Электронная почта]
Суть задачи сводится к поиску оптимальной стратегии в игре Zuma, с одним только отличием, что нет минимального количества рядом стоящих шариков, которые могут быть удалены за один раз. В обычной игре это число равно 3. На spoj.pl есть задача ZUMA, в которой как раз фигурирует это минимальное значение рядом стоящих шариков.
Решать будем двумерной LR динамикой. В таблице dp[i][j] находится оптимальный ответ для подмассива с i-ого по j-ый элементы. Базой динамики будут служить два факта:
1) if (i > j)  dp[i][j] = 0
2) if (i == j) dp[i][j] = 1
Теперь рассмотрим общий случай для произвольных i и j:
I) Очевидно, что может быть такая ситуация, когда исходный массив можно разбить на набор  непересекающихся подмассивов и последовательно избавиться от каждого из них. Например для массива A =  {1, 2, 2, 3, 4, 5, 5, 5} это будет оптимальная стратегия. Этот случай обрабатывается в строках 40-41.
II) Отдельно стоит рассмотреть случай, когда элементы a[i] и a[j] равны. Возможно стоит сначала избавиться от подмассива [i+1, j-1], а потом за одну итерацию убрать крайние элементы за одну итерацию. Например для массива B = {1,,2,3,4,5,5,5,4,3,2,1} это будет оптимальная стратегия. Этот случай обрабатывается в строке 44.
III) Продолжим рассматривать случай, когда граничные элементы подмассива равны. Может возникнуть такая ситуация, когда есть элемент a[i] == a[k] == a[j], причем i < k < j. При этом выгодно сначала избавиться от подмассива [i+1,k-1], чтобы элементы a[i] и a[k] встали рядышком, либо же избавиться от подмассива [k+1,j-1], чтобы рядом оказались элементы a[k] и a[j]. Например для массива С = {1,2,3,4,3,2,1,5,6,7,6,5,1} оптимальной стратегия будет III с элементами II(для удаления подмассивов межды единицами). Этот момент обрабатывается в строках 45-49. 
   Задача B.
   [Плитки]
Шикарная задача на динамику по рванному краю(динамика по профилю). 
Будем заполнять таблицу dp[clr][len][mask], где clr – цвет, на который заканчивается последовательность длины len, удовлетворяющая битовой маске mask. Разберемся с битовой маской.
Сразу оговоримся, что предложенное решение использует маску, ориентированную на несимметричную матрицу цветов. Условно обозначим 3 возможных цвета как R,G и B. Тогда имеем матрицу:
   R G B
R  0 1 2
G  3 4 5
B  6 7 8
На пересечении цветов указано значение row * 3 + col, где row – номер строки, col – номер столбца. Получаем следующий массив:
8  7  6  5  4  3  2  1  0   - номер сочетания цветов
BB BG BR GB GG GR RB RG RR  - сочетание цветов
Пусть номер сочетания цветов указывает на бит в маске. 
Зафиксируем для таблицы dp значение clr, len и mask. Номер единичного бита в mask говорит о том, что сочетание цветов, соответствующего номеру бита уже было в конце строки в диапазоне [len,n-1].
Отсюда можно получить базу динамики. Перебрав все пары цветов c1 и с2, в случае валидной комбинации c1-c2 dp[c1][n-2][code(c1,c2)] = 1. Случай, когда длина строки равна 1 можно рассмотреть отдельно.
Подсчет всех остальных значений отображен в строках 104-120:
Для фиксированных c1, c2, len, mask можно однозначно определить ответ:
dp[c1][len][mask] = dp[c2][len+1][mask] + dp[c2][len+1][mask ^ cur_mask], где cur_mask – закодированная комбинация цветов c1 и с2. Говоря другими словами последовательность, заканчивающаяся цветом c1 длины len и маской mask могла получиться из строки, заканчивающейся цветом c2, длины len+1 с той же маской, а также маской, в которой ранее не использовалось сочетание цветов c1 и с2.

Ответ формируется из элементов dp[c][0][mask], где с принимает все возможные значения цветов, а mask принимает все возможные валидные комбинации цветов, содержащие всю матрицу цветов.
   Задача C.
   [Симпатичные узоры возвращаются]
Задача является логическим продолжением задачи Симпатичные узоры, которое наверное является классикой динамики по рваному контуру. Ее разбор дан в лекции. Здесь лежит мое решение.
Исходная задача также разобрана в лекции. Суть ее сводится к быстрому перемножению матриц. Данный подход использовался в алгоритме для нахождения достижимости за k шагов произвольной вершины j из произвольной вершины i. Там нужно было возвести исходную матрицу смежности в степень k.