Ситуация описанная выше не такая уж и редкая, и её можно встретить во многих задачах. В том числе и задачи про монетки. И чтобы быть готовыми написать алгоритм сдачи, которые работает быстро и четко, нам нужно разобраться с проблемами чисел Фибоначчи
Динамическое программирование – это метод оптимизации алгоритмов, в основе которого лежат рекуррентные уравнения, по типу того что я приводил выше при описание последовательности Фибоначчи. По сути слово программирование, здесь не имеет в общеупотребительном толкование смысла. Тут уместней будет заменить его на “оптимизация”.
Для использования этой методики нам нужно разбить задачу на подзадачи до того момента пока мы не дойдём до примитивного решения которое можно решить здесь и сейчас. А потом объединить решения и тем самым решить основную задачу.
Это налагает определенные ограничения. Мы можем использовать этот метод только если есть:
- Оптимальная подструктура.
- Перекрывающиеся подзадачи.
Оптимальная подструктура
Это означает что если мы правильно решим подзадачи, то сможем на основе этого правильно решить основную задачу. Если наша основная задача найти F(N), где F функция которая возвращает N-ое число в последовательности. И мы определили эту функция как F(N) = F(N-1) + F(N-2) то тогда мы можем говорить об оптимальной подструктуре.
Если мы найдём решение для F(N-1) и F(N-2), то на основе этого мы сможем построить оптимальное решение. Оптимальная подструктура может отсутствовать, из-за этого мы не можем применять данную методику.
Например, если перед нами стоит задача
Перекрывающиеся подзадачи
При решение основной задачи мы встречаемся с повторяющимся подзадачами. Если посмотреть на наш граф выполнения, приведённый выше. Мы заметим что во-время решения основной задачи F(N) мы часто прибегаем к повторном решению подзадач.
Мы можем обнаружить что при F(N) мы два раза будем искать F(N-2) что в свою очередь приведёт к повторному поиску F(N-3) и F(N-4). Техники динамической оптимизации нацелены на исправление этого недостатка с помощью двух способов – нисходящего и восходящего решения.
Два пути
Нисходящий – мемоизация
Первый путь очень прост, на самом деле всё описываемое здесь просто, хоть и имеет серьезную научную основу. Нисходящий подход заключается всё в том же рекурсивном описании, но здесь неспроста стоит слово “мемоизация”.
Смысл заключается в том, что мы запоминаем предыдущее решение, и если мы уже решали задачу F(N-2) то повторно её решать не будем и возьмем решение которые мы запомнили. Это нас избавит ещё от повторного решение F(N-3) и F(N-4) и т.д.
Фрагмент 2.50
private static Dictionary<int, int> _fibonacciResults = new Dictionary<int, int>();
static int FibonacciMemoization(int n)
{
if(_fibonacciResults.TryGetValue(n, out int value))
{
return value;
}
else
{
if (n < 3) _fibonacciResults.Add(n, 1);
else
{
_fibonacciResults.Add(n, FibonacciMemoization(n - 1) + FibonacciMemoization(n - 2));
}
}
return _fibonacciResults[n];
}В этой реализации мы использовали словарь входящий в пространство имен System.Collections.Generic. С его помощью мы запоминаем предыдущие решения, и возвращаем их если они у нас имеются. Такое решение работает в разы быстрей хоть и занимает больше памяти. Это нормально, при оптимизации есть золотой закон – улучшая скорость работы мы начинаем тратить больше памяти.
В подобных случаях не всегда есть смысл использовать именно словарь. Здесь он приведён только для того, чтобы более наглядно показать, что мы “запоминаем” некоторое решение.
При использования подхода сверху вниз, порядок решения задач опять-таки диктуется сверху. Этот способ на самый оптимальный, но зачастую подходящий. По этому на нём всегда можно остановится если он выдал приемлемый результат.
Восходящий – табуляция
В предыдущий раз мы шли сверху вниз и спускали до примитивного решения. Сейчас пойдём от обратного, и пойдем снизу вверх воспользовавшись техниками восходящего анализа.
Мы заранее решаем подзадачи и так же откладываем их решение. Этот подход быстрей за счёт того, что нет накладных расходов на вызов функций. Но в некоторых случаях мы можем решить больше задач чем на требовалось бы для поиска оптимального решения.
Суть заключается в том, что мы сначала находим решение для F(0), F(1) потом F(2) и т.д пока не дойдём до F(N). Когда мы окажемся в F(N) мы будем точно знать что у нас есть решения F(N-1) и F(N-2)
Фрагмент 2.51
static int Fibonacci(int n)
{
int[] data = new int[n + 1];
data[0] = 0;
data[1] = 1;
for(int i = 2; i < data.Length; i++)
{
data[i] = data[i - 1] + data[i - 2];
}
return data[n];
}Сходное решение именно этой задачи, можно представить ещё таким образом.
Фрагмент 2.52
static int Fibonacci(int n)
{
if (n < 3) return 1;
int result = 1;
int old = 1;
for(int i = 2; i < n; i++)
{
int temp = old;
old = result;
result += temp;
}
return result;
}Оно отличается от предыдущего тем, что мы не запоминаем все решения, а только те, что нам понадобятся далее. И данная реализация не универсальна и возможна только в нашей ситуации. Подобные решения могут получатся сами по себе, без осмысления задачи в терминах динамического программирования и в этом нет ничего страшного.