Классические задачи динамического программирования. Практика 2

1.

Классические задачи динамического
программирования
Практика 2

2.

Черепашка
На квадратной доске расставлены целые неотрицательные числа. Черепашка,
находящаяся в левом верхнем углу, мечтает попасть в правый нижний. При этом она
может переползать только в клетку справа или снизу и хочет, чтобы сумма всех чисел,
оказавшихся у нее на пути, была бы максимальной. Определить эту сумму.
Полный перебор всех вариантов – универсальный способ решения. В этом случае,
например, для таблицы размером 4х4 будет 20 путей, что потребует 100 операций
сложения при подсчете сумм чисел (длина пути равна 6), для таблицы размером 8х8 –
3432 пути (44616 операций), для таблицы размером 31х31 - -1017 путей и -59х1017
операций сложения (что потребует несколько десятков лет вычислений).

3.

Рассмотрим другой способ решения
задачи. Определим подзадачу как ту
же самую задачу, но для таблицы
меньшего размера. Например, для
таблицы размером 3х4 подзадача –
это решение для таблиц с размерами
1х2, 2х1, 2x2, 1x3, 2x3, 3x2 и т.д. Для
таблиц размеров 1x2, 1x3, 1x4
движение Черепашки происходит
только вправо, поэтому сумма
стоимости клеток считается
однозначно. Аналогично для таблиц
размером 2х1, 3х1.
Для запоминания промежуточных
результатов будем строить вторую
таблицу B, для каждой клетки которой
будет хранить максимальную длину
пути до нее.
Тогда первая строка и первый столбец
этой таблицы будут выглядеть
следующим образом:

4.

Рассмотрим теперь таблицу
размером 2х2, являющуюся
фрагментом исходной таблицы.
Для трех клеток максимальный
путь уже вычислен. Очевидно, что
у Черепашки есть два способа
попадания в правую нижнюю
клетку – слева или сверху.
Выбираем тот, который дает
максимальную сумму, то есть
получим значение 4+max(5,7)=11.
Далее аналогично будем
рассматривать таблицы размером
2х3 (7+max(11,15))=22 и т.д. В
итоге, получим

5.

К-ичные числа
Требуется вычислить количество N-значных чисел в системе счисления с
основанием K, таких что их запись не содержит двух подряд идущих нулей.
Ограничения: 2 <= K <= 10, N + K <= 18.
Все числа можно разделить на три класса:
1) числа, в которых нет двух подряд идущих нулей и в конце стоит не 0;
2) числа, в которых нет двух подряд идущих нулей и в конце стоит один 0;
3) числа, в которых есть два подряд идущих нуля.
При добавлении очередной цифры к числу 1 класса мы получим либо число 1
класса (если это был не 0), либо число 2 класса (если добавим 0).
При добавлении очередной цифры к числу 2 класса мы получим либо число 1
класса (в конце не 0), либо число 3 класса (добавим еще один 0)
При добавлении любой цифры к числу 3 класса получим снова число 3 класса.
Обнозначим nz – количество чисел 1 класса, oz – количество чисел 2 класса, tz –
количество чисел 3 класса
Пусть n=1. Тогда nz=k-1, oz=1, tz=0;

6.

Пусть нам известно количество чисел в каждом классе для (n-1) цифры. Тогда для
вычисления количества n-значных чисел в трех классах воспользуемся
следующими рассуждениями.
Количество чисел в 1 классе для n-значных чисел будет равно количеству чисел 1
класса для (n-1) значных чисел, умноженное на (k-1) (количество ненулевых цифр в
k-ичной системе счисления). К этому же количеству добавится количество (n-1)значных чисел 2 класса, умноженное на (k-1).
Количество чисел во 2 классе для n-значных чисел будет равно количеству (n-1)значных чисел 1 класса (к каждому из них добавим 0, но количество чисел от этого
не изменится)
Количество чисел во 3 классе для n-значных чисел будет равно количеству (n-1)значных чисел 3 класса, умноженное на k и плюс количество (n-1)-значных чисел 2
класса (к каждому из них добавить еще по одному нулю).

7.

Подсчет количества вариантов решения.
Последовательность из 0 и 1.
Требуется подсчитать количество последовательностей длины N , состоящих из 0 и
1, в которых никакие две единицы не стоят рядом.
Если воспользоваться полным перебором, то, например, для N=64 потребуется
сгенерировать 264 последовательностей из нулей и единиц и проверить каждую из
них на соответствие условию задачи, что неэффективно по времени.
Присвоим начальные значения динамики: F[1]=2; F[2]=3. Это будет база динамики.
Правило перехода динамики – F(i+1)=F(i)+F(i-1) => F(N).
Cложность такого решения O(N).

8.

Задача о наибольшей возрастающей
подпоследовательности
В ней требуется найти оптимальное решение и восстановить ответ.
Дана последовательность, требуется найти длину её наибольшей возрастающей
подпоследовательности. Подпоследовательностью последовательности называется
некоторый набор её элементов, не обязательно стоящих подряд.
Входные данные
В первой строке входных данных задано число N - длина последовательности (1 ≤ N
≤ 1000). Во второй строке задается сама последовательность (разделитель пробел). Элементы последовательности - целые числа, не превосходящие 10000 по
модулю.
Выходные данные
Требуется вывести длину наибольшей строго возрастающей подпоследовательности и саму наибольшую возрастающую подпоследовательность.

9.

Идея решения
Определим для каждого i – номера элемента в последовательности ту наибольшую
возрастающую подпоследовательность, которая построена из элементов промежутка
[a0,..,ai] и заканчивается элементом ai. В массиве d[] будем в качестве d[i] хранить
количество элементов в соответствующей НВП, заканчивающейся элементом a[i].
База динамики. d[0]=1. Длина НВП для одного первого символа равна 1. В качестве НВП в
данном случае выступает сам элемент.
Правило перехода динамики. Предположим, что каждое d[i] – уже вычисленное для
каждого элемента i оптимальное значение длины НВП, состоящей из подходящих
элементов последовательности [a0,..,ai] и заканчивающейся элементом a[i]. Чтобы
определить d[i+1] надо посмотреть все предыдущие элементы d[0..i], для которых
выполняется a[i]<a[i+1], выбрать наибольший такой элемент d[k] и прибавить к нему 1. То
есть, найти в предыдущей последовательности наибольшую длину НВП, заканчивающуюся
элементом, меньшим, чем текущий элемент a[i] последовательности.