Занятие 9

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

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

Если множество подзадач имеет простую структуру и имеется некоторый параметр `k`, который уменьшается при разбиении на подзадачи, то можно применять динамическое программирования, не используя рекурсию: для этого в начале нужно вычислить ответ для всех подзадач с наименьшим `k` и записать их в таблицу, затем для всех подзадач со вторым по величине `k` и т.д., пока не вычислим ответ для исходной задачи. Решение задачи получается снизу вверх, от элементарных задач движемся к общей задаче.

В общем случае можно использовать запоминающие функции, запоминая результат в таблице или в map. Решение задачи получается сверху вниз, от общей задачи движемся к элементарным. В случае явного параметра `k` лучше табличный способ решения, который не имеет ограничений, связанных с размером стека для организации рекурсивного вызова функции. Этот способ решения также позволяет съэкономить на объеме необходимой памяти, так как можно хранить только `(k-1)`-ю и `k`-ю строку таблицы. Если требуется вывести не только значение оптимума, но и само оптимальное решение, то нужно запоминать для каждого оптимального решения, как оно было получено.

Определить, сколькими различными способами можно подняться на `N`-ю ступеньку лестницы, если за один шаг можно подниматься на следующую ступеньку или через одну.

Определим подзадачу `T(i)` нашей задачи, как количество способов подъема на i-ю ступеньку.

Исходя из условия задачи, на `i`-ю ступеньку можно подняться непосредственно с `(i-1)`-й и `(i-2)`-й ступенек. Поэтому, если мы знаем количество способов подъема `T(i-1)` и `T(i-2)`, то количество способов подъема на `i`-ю ступеньку может быть определено как `T(i)\ =\ T(i-1)\ +\ T(i-2)`.

Элементарными задачами являются `T(1)=1` и `T(0)=1`, для которых существует только один способ (подняться на 1 ступеньку и не делать ни одного шага).

Для решения задачи необходима одномерная таблица.

long double t[100];
long double k(int n)
{ 
  t[0]=1;
  t[1]=1;
  for(i=2;i<=n;++i)
    t[i]=t[i-1]+t[i-2];
  return t[i];
}

Тоже, но с использованием запоминающей функции:

long double t[100];
long double k(int n)
{ 
  if(t[n]) return t[n];  
  if(n<=1) return t[n]=1;
  return t[n]=k(n-1)+k(n-2);
}