реализовать DP для рекурсивной функции

Question

У меня есть следующая рекурсивная функция:

typedef unsigned long long ull; 

ull calc(ull b, ull e) 
{ 
    if (!b) return e; 
    if (!e) return b; 
    return calc(b - 1, e - 1) + calc(b - 1, e) - calc(b, e - 1); 
} 

Я хочу, чтобы реализовать его с динамическим программированием (т.е. с использованием памятью). Я попытался использовать map<pair<ull, ull>, ull>, но он слишком медленный. Я не мог реализовать его с помощью массивов O(1).

Я хочу найти решение, чтобы эта функция быстро решалась для больших b, e.

Answer 1

Если представление снизу вверх - это то, что вы хотите, тогда это будет хорошо.

Заполните таблицу MBO показал

Это может быть сделано как:

for e from 0 to n: 
    DP[0][e] = e 
for b from 0 to n: 
    DP[b][0] = b 
for i from 1 to n: 
    for j from 1 to n: 
     DP[i][j] = DP[i-1][j-1] + DP[i-1][j] - DP[i][j-1] 

теперь ваш ответ для любого Ь, е просто DP [б] [е]

Answer 2

Сделайте таблицу b/e и заполните ее ячейкой по ячейке. Это DP с пространством и временной сложностью O (MaxB * MaxE).

Сложность пространства может быть уменьшена с предложением Анте в комментарии - хранить только две необходимые строки или столбцы.

0 1 2 3 4 5 
1 0 3 . . . 
2 . . . . . 
3 . . . . . 
4 . . . . . 

Answer 3

Вы можете взглянуть на это недавнее blog posting на общем назначении автоматического memoization. Автор обсуждает различные структуры данных, такие как std::map, std::unordered_map и т. Д. Предупреждение: использует шаблон-тяжелый код.

Answer 4

Вы можете реализовать в O (n^2) (считая n как максимальное число значений для b и e) с использованием двумерного массива. Каждое текущее значение для i, j будет зависеть от значения в i-1, j и i-1, j-1 и i, j-1. Убедитесь, что вы обрабатываете случаи для i = 0, j = 0.