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

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

1) Перекрывающиеся подзадачи
2) Оптимальная подструктура
Перекрывающиеся подзадачи
В динамическом программировании вычисленные решения подзадач хранятся в таблице, поэтому их не нужно вычислять заново. Таким образом, динамическое программирование бесполезно, когда нет общих (перекрывающихся) подзадач, потому что нет смысла хранить решения.
Оптимальная подструктура
Данная проблема обладает свойством оптимальной подструктуры, если оптимальное решение данной проблемы может быть получено с использованием оптимальных решений ее подзадач.

Например, задача о кратчайшем пути имеет следующее свойство оптимальной подструктуры: если узел x лежит на кратчайшем пути от исходного узла u к узлу назначения v, то кратчайший путь от u -> v представляет собой комбинацию кратчайшего пути от u -> x и кратчайший путь от x -> v .

Стандартный алгоритм кратчайшего пути для всех пар, как Флойд-Уоршалл, и алгоритм Беллман-Форд , являются типичными примерами динамического программирования.
способы хранения значений
Существует два разных способа хранения значений, чтобы можно было повторно использовать значения подзадачи:

  1. Табуляция: снизу вверх
  2. Мемоизация: сверху вниз
Метод мемоизации
Мы инициализируем массив поиска со всеми начальными значениями как None.

Когда нужно решение подзадачи смотрим в таблицу поиска, eсли есть предварительно вычисленное значение, возвращаем это значение, в противном случае вычисляем значение и помещаем результат в таблицу поиска.
Число Фибоначчи

def fib(n, lookup):

    if n <= 1:
        lookup[n] = n
    if lookup[n] is None:
        lookup[n] = fib(n-1, lookup) + fib(n-2, lookup)
    return lookup[n]


if __name__ == "__main__":
    n = 34
    lookup = [None] * 101
    print(fib(n, lookup))
Метод Табуляции
Табулированная программа для данной задачи строит таблицу восходящим образом и возвращает последнюю запись из таблицы. Например, для одного и того же числа Фибоначчи мы сначала вычисляем fib(0), затем fib(1), затем fib(2), затем fib(3) и так далее. В буквальном смысле мы строим решения подзадач снизу вверх
Число Фибоначчи

def fib(n):

    f = [0] * (n + 1)
    f[1] = 1
    for i in range(2, n + 1):
        f[i] = f[i - 1] + f[i - 2]
    return f[n]


if __name__ == "__main__":
    n = 34
    print(fib(n))
Как классифицировать проблему
  • Ряд задач могут быть решены с помощью динамического программирования, требующие:
    • максимизации или минимизации определенных величин,
    • задачи подсчета, требующие подсчета композиций при определенных условиях,
    • определенные задачи вероятности.
  • Все задачи динамического программирования удовлетворяют свойству перекрывающихся подзадач, и большинство классических динамических задач также удовлетворяют свойству оптимальной подструктуры.
Описание задачи
Определяем в задачи основное состояние и переход.

Состояние определяется как набор параметров, которые однозначно идентифицируют определенную позицию.
Переход определяется алгоритмом перехода элемента из одного примера состояния в другое.

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