Задание ЕГЭ №18. Динамическое программирование (1)
Задание 18 ЕГЭ - задача, которая решается методом динамического программирования. Она требует понимания базового принципа ДП. Давайте разберем ее, но сначала нам нужно понять, что такое ДП.
"Динамика" - метод решения задачи путем разбиения её на более мелкие подзадачи, ответы на которые связаны между собой и итоговым ответом.
Существует множество классических задач на тему ДП, но для понимания (как решать 18ое задание) возьмем две: про кузнечика и про черепашку.
Задача про кузнечика
Условие. Дано число N и числовая последовательность от 0 до N. Кузнечик стартует с числа 0 и может прыгнуть строго либо на число i+1, либо на число i+2 (где i - текущее положение кузнечика). Вопрос: сколько существует способов допрыгнуть до числа N?
Вот простая визуализация задачи для понимания при N = 6:
Заметим, что для каждого i (i >= 2) ответом на данный вопрос будет сумма способов добраться до числа i-1 и i-2.
Заведем целочисленный (int / long long) массив, который будет показывать, сколько есть способов добраться до числа i, назовем его dp (dp[i] - это кол-во способов добраться до числа i).
Весь код будет записан псевдокодом.
dp = []
Мы знаем, что способов добраться до dp[0] - ноль, до dp[1] - один, а до dp[2] - два (потому что мы можем добраться с нулевой и первой клетки).
dp[0] = 0 dp[1] = 1 dp[2] = 2
Но что дальше? Мы сказали ранее, что до числа i мы можем добраться с чисел i-1 и i-2. А их значения в массиве dp нам помогут узнать ответ на данный вопрос (потому что мы уже посчитали кол-во способов для i-1 и i-2).
перебор переменной i от 3 до N:
dp[i] = dp[i - 1] + dp[i - 2] Где же будет находиться ответ? Это кол-во способов добраться до числа N, поэтому - в dp[N].
вывод dp[N]
Вопрос для засыпку. А как связан данный метод решения задачи с заданием на нахождение кол-ва путей в графе (задание 13 ЕГЭ)? И как решить ее методом ДП?
Задача про черепашку
Условие. Дан двумерный массив NxN (где N - размер столбца/строки). Черепашка стоит в первой клетке первого столбца. Она может двигаться либо вправо, либо вниз. В конце концов, она дойдет до клетки с координатами (N, N). В клетках массива (таблицы) содержатся некоторое число монет a[i][j]. Найти максимальное значение монет, которое может собрать черепашка.
Визуализируем задачу. Вот массив a размера N = 4 и числа в нем, а также оптимальный путь черепашки для данного массива a (ответ - 25).
Рассмотрим первую клетку первого столбца. Черепашка стоит там изначально. Поэтому значение собранных монет там будет равно a[1][1] (условимся, что это значение первой клетки первого столбца).
Запишем это в двумерный массив dp[][].
dp = [][] dp[1][1] = a[1][1]
Рассмотрим случай, когда черепашка идет вправо до конца. Тогда значение dp[1][i] будет равно
перебор переменной i от 2 до N:
dp[1][i] = dp[1][i-1] + a[1][i]Действительно, пойдя до конца вправо мы соберем все монеты в первой строке. И это будет максимальным значением для каждой клетки первой строки (помним: наша задача - максимизировать данное значение).
Аналогично делаем для первого столбца:
перебор переменной i от 2 до N:
dp[i][1] = dp[i-1][1] + a[i][j]Таким образом, так выглядит наш двумерный массив dp после выше перечисленных действий для примера (также выше).
Но что делать с остальными клетками?
Наша задача, напоминаю, состоит в максимизации числа монет.
Поэтому для каждой dp[i][j] (i > 1, j > 1) справедливо следующее выражение:
перебор переменной i от 2 до N:
перебор переменной j от 2 до N:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + a[i][j]
Для клетки с координатами (2,2) выгоднее выбрать максимум из клетки сверху и клетки слева (по условию) и прибавить значение a[2][2] = 2 (см. изначальный пример). Тогда dp[2][2] = 10.
Таким образом, мы делаем это до клетки с координатами (N, N).
Ответ лежит в dp[N][N]. Задача решена.
Теперь задача ЕГЭ
Как это связано с 18ым заданием ЕГЭ?
Здесь такой же массив чисел, так же, как и черепашка, двигается робот. Но имеются стенки.
Рассмотрим следующую таблицу, прилагаемую к данному заданию.
Продублируем таблицу и проделаем аналог действий для решения задачи про черепашку.
# клетка в изначальной таблице - клетка, соответствующая месту клетки в первой таблице. в первом столбце со второго элемента: =(клетка сверху)+(клетка в изначаль- ной таблице) в первой строке со второго элемента: =(клетка слева)+(клетка в изначальной таблице) во всех остальных: =макс(клетка сверху;клетка слева)+(клетка в изначальной таблице)
Не забудем вставить формат клеток во вторую таблицу (где мы проводили данные действия).
Желтым цветом отмечены клетки таблицы, которые ограничены стенкой. Для их значений нельзя брать максимум из двух элементов, поэтому формула для этих клеток преобразуется в
= (клетка сверху/слева) + (клетка в изначальной таблице)
Ответ лежит в последней клетке последнего столбца.
Но это только часть ответа, потому что нас просили также найти минимум. Для этого нам необходимо применить Ctrl+H (предварительно выделив вторую таблицу) -> заменить все "макс" на "мин").
Вторая часть ответа также лежит в последней клетке последнего столбца.