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

Блог пользователя Trytrytry

Автор Trytrytry, 13 лет назад, По-русски

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

Пример:

1. С запоминаем и рекурсией

int mem[100]; //memset(dp,255,sizeof dp);

int rec(int n)

{

if(n <= 1) return 1;

if (mem[n] != -1) return mem[n];

mem[n] = rec(n - 1) + rec(n - 2);

return mem[n];

}

2. C циклами

int dp[100];

dp[0] = dp[1] = 1;

for (int i = 2; i < n; i++)

dp[i] = dp[i - 1] + dp[i - 2];

Просто уж очень часто замечаю что некоторые пишут так некоторые так, вроде как и так так не плохо.
Какой метод вы используете чаще и почему?

дп

-4

Trytrytry
13 лет назад
13

Комментарии (13)

Написать комментарий?

riadwaw

13 лет назад, # |

+10

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

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

→ Ответить

Trytrytry

13 лет назад, # ^ |

Может ли этот оверхед как-то сильно помешать?

Просто заметил что рекурсию всегда легче делать, чем циклы.

→ Ответить

yeputons

13 лет назад, # ^ |

Может. У меня было такое. А вот насколько сильно он реально мешает - надо эксперементировать.
А вот мне иногда циклами писать проще. Например, 500-ю с последнего SRM. Там сразу очевидно, в каком порядке считать и не разрастается код из-за int calc(...).

→ Ответить

riadwaw

13 лет назад, # ^ |

Не согласен с тем, что рекурсия всегда в проще.

Даже в вашем примере цикл писать куда удобнее)

→ Ответить

acherepanov

13 лет назад, # |

+14

Чем хороша ленивая динамика:

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

А итеративная реализация может существенно выиграть в скорости за счет последовательного вычисления значений функции (последовательные куски массива кэшируются) и отсутствия рекурсивных вызовов.

Есть еще так называемая "динамика вперед". Иногда нам известны не те значения, которые нужны, чтобы вычислить данное, а наоборот - для каких значений наше дает вклад. Ясное дело, можно построить соответствующий граф и поменять в нем ориентацию ребер, но динамика вперед удобнее =) Рекурсивный вариант этой версии мне неизвестен.

→ Ответить

yeputons

13 лет назад, # ^ |

Исключительные ситуации легко лечатся методом "посчитаем ответ для n=0, m=0" ручками. Обычно ответы там тривиальные...

→ Ответить

acherepanov

13 лет назад, # ^ |

Пусть в цикле ты перебираешь все перестановки, а map'ом пользоваться не хочется. Тогда в отдельной функции можно по перестановке получать ее номер и обращаться уже к элементу массива.

→ Ответить

imslavko

13 лет назад, # |

Вопрос, вроде как и по-теме топика:

При использовании ленивой динамики, есть вероятность переполнения стека рекурсии. Как посчитать, хватит ли мне стека или как его увеличить в GNU g++? (насколько я знаю, #pragma comment(linker: ...) работает для VS)

Как написать рекурсию своим ручным стеком? У меня с этим проблемы. Не могу даже dfs стеком написать, например поиск мостов.

→ Ответить

yeputons

13 лет назад, # ^ |

В GCC это можно только прописать в параметрах компиляции: -Wl,--stack=<размер в байтах>.
А насчёт ручного стека - вот тут выложил кусок непонятного кода.
Если надо, могу в сегодня-завтра написать пост про ручной стэк.

→ Ответить

imslavko

13 лет назад, # ^ |

Допустим я на соревновании. Не проходит задача из-за стековерфлоу. Организаторы соревнования не втыкают, что за стек и как его увеличить. Было бы проще прописывать строку увеличения стека везде, где только можно, ведь это зависит от меня, участника. Но вещи, которые зависят от организаторов - на них я не могу оказать влияния

→ Ответить

yeputons

13 лет назад, # ^ |

Да, увы. Поэтому задачи с stackoverflow надо сдавать либо на MSVC, либо на GCC, убедившись, что в стэк залезет.

→ Ответить