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

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

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

Учебные задачи:
   Задача A.
   [Взрывоопасность]
Очевидно, если N = 1, то возможны два варианта: “А” и “B”. Если N = 2, то можно получить сразу две последовательность, заканчивающиеся на ‘B’, приписав ее к каждой последовательности, получившейся на предыдущем шаге, т.е. последовательности “AB” и “BB”. ‘A’ можно приписать только к одной последовательности “B”, получив “BA”. Итого, для N = 2 получили 3 варианта. Обозначим dp[i] – количество вариантов, которые можно получить из i-блоков. Продолжая рассуждения в той же духе можно заметить, что для любого i можно получить dp[i-1] последовательностей, приписав к ним блок ‘B’, а также dp[i-2] последовательностей, которые заканчиваются на ‘B’, к которым можно приписать блок ‘A’. В итоге получаем рекуррентную формулу dp[i] = dp[i-1] + dp[i-2]. Что является формулой вычисления числе Фибоначчи.
В классическом виде данная задача формулируется так: сколькими способами можно записать последовательность длины N из 0 и 1 без двух подряд идущих нулей. 
   Задача B.
   [Наибольшая возрастающая подпоследовательность (НВП)]
Данную задачу мы уже решали несколько раз [1C из курса Меньшикова]. Но всегда полезно повторить изученное. В данном решении я привел квадратичное решение. С более быстрым решением можно ознакомится в разборе задачи 1C.
   Задача C.
   [0-1 Рюкзак]
Классическая задача на ДП, которую нужно уметь решать. На каждом шаге пытаемся набрать вес(j+w[i]), который формируется из веса гарантировано набранного на предыдущих шагах(j) + веса текущей вещи(w[i]). Стоимость такой новой комбинации формируется из стоимости вещей, набранных на предыдущем шаге(dp[j]) + стоимость текущей вещи(p[i]). Если получается так, что новая стоимость для веса j+w[i] более предпочтительна, т.е. превышает стоимость, полученную для этого веса на предыдущих шагах, то нужно обновить ее с учетом i-ой вещи. Суть сказанного иллюстрирует эта строка:

dp[j+ w[i]] = max(dp[j+ w[i]], dp[j] + p[i]);

Отметим тот факт, что изначально весь массив dp заполнен –1, а dp[0] = 0.
Олимпиадные задачи:
   Задача A.
   [Покупка билетов]
На каждом этапе пытаемся получить оптимальный ответ для первых N человек. Возможно лучшим решением было бы завести первые три барьерных элемента, но я ручками подсчитал первые три решения для n = 0,1 и 2, а дальше запустил цикл с рекуррентной формулой. 
   Задача B.
   [Две стены]
Сразу сделаем важную оговорку. Необходимо использовать все кирпичи в наборе. Поэтому если вдруг получилось так, что сумма длин всех кирпичей цвета A не равна сумме длин кирпичей цвета B, значит построить две прямоугольные стены уже не получится. Будем использовать подход, который использовали в решении задачи о рюкзаке. А именно будем искать все возможные комбинации длин, которые можно получить из кирпичей одного цвета. Пусть SUM – сумма длин всех кирпичей одного цвета. Тогда необходимо найти такое значение SEP, что для каждого цвета можно набрать длину SEP и SUM-SEP. Если это сделать удалось, значит решение найдено.
   Задача C.
   [Репортаж]
Задача легко решается, что мы умеем решать задачу B из предыдущего блока, где нужно находить наибольшую возрастающую подпоследовательность(LIS). Для начала найдем LIS для исходного массива, а потом проделаем тоже самое только LIS будем искать не слева направо, а справа налево. В итоге останется только найти такую позицию в исходном массиве, для которой минимальное значение меньших элементов справа и слева будет максимально.
Дополнительные олимпиадные задачи:
  Задача A.
   [Отчет]
Задача сводится к поиску максимальной подпоследовательности, в которой возрастает общий объем производства и убывает процент бракованных изделий. Суть решения мало чем отличается от поиска LIS.
   Задача B.
   [Словарь]
Для каждой позиции i в тексте будем искать слово, на которое оно может оканчиваться. Для этого можно перебрать все слова(ограничения позволяют) из словаря и проверить можно ли сформировать текст, заканчивающийся позицией i – size, где size – длина текущего слова.
   Задача C.
   [Валютные махинации]
Несложная задача. Ее можно было дать и в учебных задачах, потому как она позволяет прочувствовать суть ДП на простом примере. Для каждого дня будем искать максимальное количество рублей, долларов и евро, которое можно получить за первые дни, оканчивающихся текущим. Максимальное количество рублей для текущего дня будет равно максимальному из значений:
1) Максимальное количество рублей с предыдущего дня
2) Максимальное количество долларов с предыдущего дня, переведенное по сегодняшнему курсу в рубли. 
3) Максимальное количество евро с предыдущего дня, переведенное по сегодняшнему курсу в рубли.
Доллары и евро ищутся по схожей схеме.