Как вы считаете есть ли существенная разница (в сложности вычислений, итп) между двумя(тремя, четырьмя,...) техниками динамического программирование, рекурсивного с запоминанием и циклов с массивами.
Пример:
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];
Просто уж очень часто замечаю что некоторые пишут так некоторые так, вроде как и так так не плохо.
Какой метод вы используете чаще и почему?
Какой метод вы используете чаще и почему?
А вот мне иногда циклами писать проще. Например, 500-ю с последнего SRM. Там сразу очевидно, в каком порядке считать и не разрастается код из-за int calc(...).
Вопрос, вроде как и по-теме топика:
При использовании ленивой динамики, есть вероятность переполнения стека рекурсии. Как посчитать, хватит ли мне стека или как его увеличить в GNU g++? (насколько я знаю, #pragma comment(linker: ...) работает для VS)
Как написать рекурсию своим ручным стеком? У меня с этим проблемы. Не могу даже dfs стеком написать, например поиск мостов.
А насчёт ручного стека - вот тут выложил кусок непонятного кода.
Если надо, могу в сегодня-завтра написать пост про ручной стэк.
Небольшая ошибка в коде вот тут:
if(n < 1) return 1;
или в коде уже исправлено?