Динамическое программирование — основы

  • Краткая история
  • Определение
  • Общие принципы
  • Кузнечик
  • Черепашка
  • Восстановление ответа в динамике

  • Ещё несколько задач *
    • Последовательности без 3 единиц подряд
    • Лесенки

Краткая история

В конце 1950 года Ричард Беллман работал в RAND Corp. Он занимался многоступенчатыми процессами принятия решений (multistage decision processes). Но эти годы не были подходящими для математических исследований. RAND Corp основали ВВС и начальство терпеть не могло слова: математика, исследования и тп. Поэтому ему пришлось придумать красивое название своей деятельности, чтобы затем спокойно заниматься математикой и исследованиями под его прикрытием.

Другими словами название динамическое программирование на самом деле ничего не означает.

Определение

Динамическое программирование — это когда у нас есть задача, которую непонятно как решать, и мы разбиваем ее на меньшие задачи, которые тоже непонятно как решать.

(с) А. Кумок.

Метод динамического программирования, который иногда называют методом динамической оптимизации - это подход к решению сложных задач путем разбиения их на более мелкие части и запоминания результатов решения этих частей.

Давайте разберем пример:
5 + 5 = ?
5 + 5 + 5 = ?
5 + 5 + 5 + 5 = ?
5 + 5 + 5 + 5 + 5 = ?

Динамическое программирование позволяет нам избежать повторений, путем запоминания промежуточных результатов. То есть путем запоминания результатов проблем, которые мы уже решили.

Динамическое программирования является комбинацией двух подходов: алгоритма разделяй и властвуй (divide and conquer algorithm) и жадного алгоритма (greedy algorithm).

На алгоритм разделяй и властвуй похоже тем, что мы разбиваем задачу на более мелкие части. Хотя в динамическом программировании мелкие задачи пересекаются, дополняют друг друга.

На жадный алгоритм похоже тем, что мы также сразу ищем оптимальное решение. Правда не всей задачи целиком, а отдельных подзадач. Другими словами, мы не пересчитываем решения подзадач.

Общие принципы

Рассмотрим такую задачу: найти N-е число Фибоначчи.

Числа Фибоначчи: 0 1 1 2 3 5 8 13 21 ...
Первые два числа 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел.

Эту задачу можно решить рекурсивно:

In [ ]:
int Fibonacci(const int n) {
    if (n < 0) return -1;
    else if (n < 2) return n;
    else return Fibonacci(n - 2) + Fibonacci(n - 1);
}

Однако это будет работать очень долго. 20-е число посчитать еще можно будет, а 40-е число - нет. И не потому, что числа большие. А потому, что мы будем делать слишком много лишней работы. Число операций будет экспоненциально относительно $N$.

Почему? Потому что, чтобы посчитать N-е число, нам нужно будет независимо посчитать (N-1)-е число и (N-2)-е число, и это в минимум в два раза больше действий, чем нужно для (N-2). А значит, для подсчета N-го числа Фибоначчи необходимо 2 раза посчитать (N-2)-е число, и это занимает в два раза больше времени, а значит это хотя бы $2^\frac{N}{2}$ действий.

Это ну слишком долго, и главное, что это легко исправляется. Давайте просто не считать лишних действий - если мы один раз посчитали $F_k$, то давайте запомним, чему оно равно, и в следующий раз, когда оно нам понадобится, мы используем его сразу. Удобнее всего сохранить числа Фибоначчи прямо в массиве.


Существует два основных подхода в динамическом программировании:

  • Мемоизация (ленивая динамика)
  • Табулация

Мемоизация (заполнения кеша сверху-вниз) является техникой кеширования, которая использует заново ранее вычисленные решения подзадач. Функция Фибоначчи с использованием техники мемоизации выглядела бы так:

In [ ]:
int MemFibonacci(const int n, vector<int>& mem) {
    if (n < 0) return -1;
    else if (mem[n] != -1) return mem[n];
    else if (n < 2) mem[n] = n;
    else mem[n] = MemFibonacci(n - 2, mem) + MemFibonacci(n - 1, mem);
    return mem[n];
}

int main() {
    const int n = 40;
    vector<int> mem(n + 2, -1);
    cout << MemFibonacci(n, mem);
    return 0;
}


Табуляция (заполнение кеша снизу-вверх) является схожей техникой, но которая в первую очередь сфокусирована на заполнении кеша, а не на поиске решения подпроблемы. Вычисление значений, которые необходимо поместить в кеш легче всего в данном случае выполнять итеративно, а не рекурсивно. Функция Фибоначчи с использованием техники табуляции выглядела бы так:

In [ ]:
int TabFibonacci(const int n) {
    vector<int> mem(n + 2, -1);
    mem[0] = 0;
    mem[1] = 1;
    for (int index = 2; index <= n; ++index) {
        mem[index] = mem[index - 2] + mem[index - 1];
    }
    return mem[n];
}

А можно сократить расход памяти?



Используем константную память O(1):

In [ ]:
int MemConstFibonacci(const int n) {
    if (n < 0) return -1;
    else if (n < 2) return n;

    int first = 0, second = 1, result = 0;
    for (int index = 2; index <= n; ++index) {
        result = first + second;
        first = second;
        second = result;
    }
    return result;
}

Это и называется динамическим программированием (или динамикой, ДП). Основная идея состоит в том, чтобы

  • свести задачу для $N$ к задаче для чисел, меньших, чем $N$ (с помощью формулы)
  • хранить все ответы в массиве
  • заполнить начало массива вручную (для которых формула не работает)
  • обойти массив и заполнить ответы по формуле
  • вывести ответ откуда-то из этого массива

Чтобы решить задачу по динамике вы должны ответить на 5 вопросов:

  • Что лежит в массиве? (самый важный вопрос чаще всего)
  • Как инициализировать начало массива?
  • Как обходить массив? (чаще всего слева направо, но не всегда)
  • Какой формулой считать элементы массива?
  • Где в массиве лежит ответ?


Задача: Человек на лестнице.


Одномерная динамика: кузнечик

Рассмотрим такую задачу:

Есть полоска $1\times N$, кузнечик стоит на первой клетке, он может прыгать вперед на 1, 2, 3 клетки. Сколько есть способов добраться от начальной клетки до последней?

Как решать такие задачи? Нужно придумать рекуррентную формулу, как ответ для N зависит от ответа для меньших чисел.

Очень помогает посмотреть на маленькие числа (!! одна из самых важных идей для придумывания решений):

Пусть dp[x] - это количество способов добраться от 1 клетки до клетки номер x.

  • dp[1] = 1 способ (стоять на месте)
  • dp[2] = 1 способ ($1 \rightarrow 2$)
  • dp[3] = 2 способа ($1 \rightarrow 2 \rightarrow 3$ и $1 \rightarrow 3$)
  • dp[4] = 4 способа ($1 \rightarrow 2 \rightarrow 3 \rightarrow 4$ и $1 \rightarrow 3 \rightarrow 4$ и $1 \rightarrow 2 \rightarrow 4$ и $1 \rightarrow 4$)
  • dp[5] = 7 способов ($1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5$ и $1 \rightarrow 3 \rightarrow 4 \rightarrow 5$ и $1 \rightarrow 2 \rightarrow 4 \rightarrow 5$ и $1 \rightarrow 4 \rightarrow 5$ и $1 \rightarrow 2 \rightarrow 3 \rightarrow 5$ и $1 \rightarrow 3 \rightarrow 5$ и $1 \rightarrow 2 \rightarrow 5$)

Дальше становится сложнее. Но можно заметить закономерность. А можно и не заметить, но зато если мы сейчас придумаем формулу, мы легко проверим, работает ли она. Заодно мы получили наши значения на маленьких числах, которые нам все равно понадобится вбить в программу.

Какой последний прыжок кузнечика в его пути до N-й клетки? Один из трех вариантов:

  • $(N - 1) \rightarrow N$
  • $(N - 2) \rightarrow N$
  • $(N - 3) \rightarrow N$

То есть все пути до $N$ разбиваются на 3 группы. Причем мы знаем сколько путей в каждой группе. В первой из них ровно dp[N - 1] путей - столько путей идут до (N-1)-й клетки, и дальше идет еще один прыжок. Во второй и третьей группах поэтому тоже dp[N - 2] и dp[N-3] путей.

Так что формула получается такой: dp[N] = dp[N - 3] + dp[N - 2] + dp[N - 1].

Очень похоже на числа Фибоначчи, да? Можете посмотреть на числа, которые мы уже выписали, там все отлично подходит:

dp[4] = 4 = 1 + 1 + 2 = dp[1] + dp[2] + dp[3]

dp[5] = 7 = 1 + 2 + 4 = dp[2] + dp[3] + dp[4].

Так что программа пишется легко:

In [ ]:
int Cricket(const int n) {
    vector<int> mem(n + 1, 0);
    mem[1] = 1;
    mem[2] = 1;

    for (int index = 3; index <= n; ++index) {
        mem[index] = mem[index - 1] + mem[index - 2] + mem[index - 3];
    }

    return mem[n];
}

// 0 1 1 2 4 7 13 24 44 81 149

Давайте изменим немного задачу: Теперь некоторые из клеток закрыты. То есть нам известно про конкретные клетки, что на них кузнечик прыгать не может. Тогда задача все еще решается так же, только нужно убедиться, что dp[x] = 0 для всех запрещенных x!

Также немного перепишем код, чтобы не писать отдельно случаи для 2 и 3, а также чтобы не писать в формуле сумму трех чисел (а представьте, что в задаче не 3, а 100). Будем инициализировать только dp[1]. А ко всем следующим значениям dp[i] будет прибавлять dp[i - k], где k = 1, 2, 3. Причем, если i - k < 1, то мы будем игнорировать такие клетки, и этим самым мы избавились от необходимости прописывать ответ для dp[2] и dp[3].

In [ ]:
int Cricket(const int n, const set<int>& exclude, const int steps = 3) {
    const int size = max(n + 1, steps);
    vector<int> mem(size, 0);
    mem[1] = 1;

    for (int index = 2; index <= n; ++index) {
        if (exclude.count(index) != 0) {
            continue;
        }

        for (int step = 1; step <= steps && index - step >= 0; ++step) {
            mem[index] += mem[index - step];
        }
    }

    return mem[n];
}

int main() {
    const set<int> exclude = {2, 3, 6, 13};
    for (int index = 0; index <= 10; ++index) {
        cout << cricket(index, exclude) << " ";
    }

    return 0;
}

// 0 1 0 0 1 1 0 2 3 5 10


Двумерная динамика: черепашка

Теперь рассмотрим такую задачу:

На каждой клетке двумерной таблички написано, сколько там лежит монет. Черепашка стоит в клетке 1x1 (верхней левой), и может двигаться только на одну клетку вниз, или на одну клетку вправо. Нужно найти максимальное число монет, которое может набрать черепашка по пути к нижней правой клетке NxM.

Первое, что приходит в голову - это просто идти черепашкой в ту клетку из соседних, где лежит больше монет. К сожалению, эта жадная стратегия не всегда работает. Например, на такой доске жадная черепашка пошла бы по следу из единичек, хотя гораздо выгоднее пойти сначала по нулям, а потом найти там большие горстки монет (40, 70, 100):

In [ ]:
const vector<vector<int>> coins = {
    {0,   1,   1,   1,   1,   1},
    {0,   0,   0,   0,   0,   1},
    {0,   40,  70,  0,   0,   1},
    {100, 0,   0,   0,   0,   1}
};

Тут нас снова спасает динамика. Давайте сводить задачу к предыдущей! Задачей назовем "сколько максимально монет можно набрать на пути от $0\times0$ до $i\times j$" (заменим 1-нумерацию на 0-нумерацию). Будем хранить это в двумерном массиве dp в клетке dp[i][j].

Сразу понятны некоторые свойства этого массива:

  • Он размера NxM
  • dp[0][0] = COINS[0][0]
  • ответ на всю задачу лежит в dp[N - 1][M - 1]

Но гораздо важнее придумать формулу для подсчета dp[i][j] через предыдущие. Легко посчитать первую строку и первый столбец:

  • dp[0][k] = dp[0][k - 1] + COINS[0][k]
  • dp[k][0] = dp[k - 1][0] + COINS[k][0]

Так как до этих клеток есть ровно один путь.

Но что делать, если есть много путей до клетки dp[i][j]? Снова разобьем их на на несколько групп в зависимости от последнего хода (! важный трюк, запомните). Последний ход был:

  • либо из [i][j - 1]
  • либо из [i - 1][j]

Поэтому формула для максимального числа монет такая: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + COINS[i][j].

Ну все, достаточно пройтись правильно по двумерному массиву (построчно сверху вних, а в каждой строке слева направо) и заполнить этот массив.

In [ ]:
int Turtle(const vector<vector<int>>& coins) {
    if (coins.empty()) return -1;
    else if (coins.front().empty()) return -1;

    const size_t rows = coins.size();
    const size_t columns = coins.front().size();
    auto mem = coins;

    for (int row = 0; row < rows; ++row) {
        for (int column = 0; column < columns; ++column) {
            int max = 0;
            if (row - 1 >= 0) max = mem[row - 1][column];
            if (column - 1 >= 0) max = std::max(max, mem[row][column - 1]);
            mem[row][column] += max;
        }
    }

    return mem[rows - 1][columns - 1];
}

// 113

В отличие от жадного алгоритма, динамическое программирование находит оптимальное решение - это, в данном случае, 113 монет.


Вопрос: Но как сэкономить на памяти?


Восстановление ответа

В последней задаче было здорово найти, что в оптимальном пути черепашки набирается 113 монет, но интересно, что именно это за путь. Такую задачу называют восстановлением ответа в динамике.

Есть два способа, которыми можно это сделать.

1) Хранить в массив prev откуда ты пришел в эту клетку.

Когда мы выбираем максимум из левой и верхней клетки, мы на самом деле решаем, какой последний ход будет в оптимальном пути до этой клетки - сверху или слева, и берем ответ для той клетки, сложнный с монетами в этой клетке. Давайте координаты клетки, откуда мы пришли, хранить в массиве prev. Или, в данном случае, можно хранить не координаты а просто 1, если пришли слева, и 0, если пришли сверху.

In [ ]:
int Turtle(const vector<vector<int>>& matrix,
           vector<vector<pair<int, int>>>& path) {
    if (matrix.empty()) return -1;
    else if (matrix.front().empty()) return -1;

    const size_t rows = matrix.size();
    const size_t columns = matrix.front().size();
    auto mem = matrix;

    for (int row = 0; row < rows; ++row) {
        for (int column = 0; column < columns; ++column) {
            if (row == 0 && column == 0) {
                continue;
            } else if (row == 0) {
                mem[row][column] += mem[row][column - 1];
                path[row][column] = {row, column - 1};
            } else if (column == 0) {
                mem[row][column] += mem[row - 1][column];
                path[row][column] = {row - 1, column};
            } else {
                if (mem[row][column - 1] > mem[row - 1][column]) {
                    mem[row][column] += mem[row][column - 1];
                    path[row][column] = {row, column - 1};
                } else {
                    mem[row][column] += mem[row - 1][column];
                    path[row][column] = {row - 1, column};
                }
            }
        }
    }

    return mem[rows - 1][columns - 1];
}

int main() {
    const std::vector<std::vector<int>> matrix = {
        {0,   1,   1,   1,   1,   1},
        {0,   0,   0,   0,   0,   1},
        {0,   40,  70,  0,   0,   1},
        {100, 0,   0,   0,   0,   1}
    };

    const size_t rows = matrix.size();
    const size_t columns = matrix.front().size();
    const vector<pair<int, int>> column(columns, {-1, -1});
    vector<vector<pair<int, int>>> path(rows, column);
    cout << Turtle(matrix, path) << endl;

    auto current = path.back().back();
    vector<pair<int, int>> points;
    while (current.first != -1 && current.second != -1) {
        points.push_back(current);
        current = path[current.first][current.second];
    }

    reverse(points.begin(), points.end());
    for (const auto& point : points) {
        cout << "(" << point.first << ",";
        cout << point.second << ") ";
    }

    return 0;
}

// (0,0) (0,1) (1,1) (2,1) (2,2) (2,3) (2,4) (2,5)

2) Вместо хранения массива prev догадаться по массиву dp, откуда именно черепашка пришла в эту клетку.

В данном примере это довольно легко. Если мы уже посчитали весь массив dp, то теперь можно начиная с конца легко понять, пришла черепашка туда сверху или слева в оптимальном маршруте - она пришла из клетки с максимальным числом монет.

In [ ]:
int row = static_cast<int>(rows) - 1;
int column = static_cast<int>(columns) - 1;
while (row != 0 && column != 0) {
    if (row == 0) {
        --row;
    } else if (column == 0) {
        --column;
    } else if (mem[row - 1][column] > mem[row][column - 1]) {
        --row;
    } else {
        --column;
    }
    path.push_back({row, column});
}
path.push_back({0, 0});
reverse(path.begin(), path.end());

Задание

Решите как можно больше задач из простого контеста:

https://informatics.msk.ru/mod/statements/view.php?id=33233#1

А также решите как можно больше задач из сложного контеста:

https://informatics.msk.ru/mod/statements/view.php?id=35808#1

Разбор еще нескольких задач

Давайте разберем еще несколько задач.

Последовательности без 3 единиц подряд

Условие:

Определите количество последовательностей из нулей и единиц длины $N$, в которых никакие три единицы не стоят рядом.

Решение:

Давайте хранить в $dp[N]$ ровно число таких последовательностей длины $N$ (это первое, что должно приходить в голову).

Давайте посмотрим для начала для маленьких чисел:

  • $dp[0] = 1 (\text{пустая последовательность})$
  • $dp[1] = 2 (0, 1)$
  • $dp[2] = 4 (00, 01, 10, 11)$
  • $dp[3] = 7 (000, 001, 010, 011, 100, 101, 110)$
  • $dp[4] = 13 (0000, 0001, 0010, 0011, 0100, 0101, 0110, 1000, 1001, 1010, 1011, 1100, 1101)$

Сходу закономерность можно не увидеть. Нужно догадаться сгруппировать эти числа по том, сколько в конце единичек. Например, для dp[4]:

  • 0 единичек в конце: $0000, 0010, 0100, 0110, 1000, 1010, 1100$ - их ровно семь, как для $N=3$, потому что первые 3 числа могут быть любые (но без трех единиц подряд), а четвертое - 0
  • 1 единичка в конце: $0001, 0101, 1001, 1101$ - их ровно четыре, как для $N=2$, потому что первые 2 числа могут быть любые (но без 3 единиц подряд), а два последних - 01
  • 2 единички в конце: $0011, 1011$ - их ровно две, как для $N=1$, потому что первое число может быть любым (но без 3 единиц подряд), а три последних - 011

Так мы замечаем и доказываем формулу: $dp[N] = dp[N-1] + dp[N-2] + dp[N-3]$

Теперь за $O(N)$ ее легко посчитать.

Лесенки

Условие:

Лесенкой называется набор кубиков, в котором каждый горизонтальный слой содержит меньше кубиков, чем слой под ним. Подсчитать количество различных лесенок, которые могут быть построены из N кубиков.

Решение:

Если считать, что $dp[N]$ - это число лесенок из $N$ кубиков, то никакой закономерности скорее всего найти не получится.

  • $dp[1] = 1$
  • $dp[2] = 1$
  • $dp[3] = 2$
  • $dp[4] = 2$
  • $dp[5] = 2$
  • $dp[6] = 3$

По числам построить закономерность сложно, и по самим лесенкам тоже. Не видно какого-то рассуждения вида "ко всем лесенкам размера N-1 можно положить на любой слой еще один кубик", иногда ведь и нельзя.

Тут нам помогает введение дополнительного параметра. Нас просят решить одномерную задачу (для $N$), а мы решим двумерную задачу для $n$ и $m$. Давайте зафиксируем размер самого нижнего слоя и назовем его размер $m$.

То есть $dp[n][m] = $"число лесенок, состоящих из $N$ кубиков, таких, что самый нижний слой состоит из $M$ кубиков".

Как это связано с нашей задачей? Ответ на нашу задачу равен $dp[N][1] + dp[N][2] + \ldots + dp[N][N]$.

Какая есть формула для такой постановки задачи? Размер нижнего слоя у нас зафиксирован и равен $m$, осталость $n-m$ кубиков на верхних слоях. Логично перебрать размер второго снизу слоя, который может быть любым от $1$ до $m-1$: $dp[n][m] = dp[n-m][1] + dp[n-m][2] + \ldots + dp[n-m][m-1]$

Это все пир условии, что $n \geq m$. Иначе $dp[n][m] = 0$.

Теперь осталось понять как инициализировать этот массив и аккуратно по нему пройтись. Давайте инициализируем его ровно для случая $n=0, m=0$:

$dp[0][0]$ = 1

Пройдемся по массиву сначала для всех m при n = 1, потому для всех m при всех n = 2 и так далее - то есть по строчкам обычными двумя циклами $for$.

Для $m > 0$ в ячейках $dp[0][m]$ наш алгоритм будет работать и возвращать 0, так как $n < m$.

Для всех $n > 0$ наша формула будет находить ответ через числа с меньшим n, а значит алгоритм корректен.

Он заполняет табличку размера $N^2$, обрабатывая каждую клетку за $O(N)$ операций, итоговое время работы - $O(N^3)$.