Динамическое программирование: Правда или Ложь

Question

У меня есть концептуальные сомнения относительно динамического программирования:

In a dynamic programming solution, the space requirement is always at least as big as the number of unique sub problems. 

Я думал, что это в терминах чисел Фибоначчи:

f(n) = f(n-1) + f(n-2) 

Здесь есть две подзадачи, требуемое пространство будет, по крайней мере, O (n), если ввод равен n. Справа?

Но, ответ False.

Может кто-нибудь объяснить это?

Answer 1

Ответ действительно ложный.

Например, в вашей серии Фибоначчи, вы можете использовать динамическое программирование с использованием O (1) пространство, помня только 2 последние цифры:

fib(n): 
    prev = current = 1 
    i = 2 
    while i < n: 
     next = prev + current 
     prev = current 
     current = next 
    return current 

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

Answer 2

Если вы используете вычисление Фибоначчи с использованием восходящего DP, вы можете отбросить ранее полученные результаты, которые вам не нужны. Это пример:

fib = [0, 1] 
for i in xrange(n): 
    fib = [fib[1], fib[0] + fib[1]] 
print fib[1] 

Как показано на этом примере, вам нужно запомнить только два последних элемента в массиве.

Answer 3

Данное заявление является неверным. Но это почти правильно.

Для динамического программирования требуется O(number of subproblems). Другими словами, если есть решение для динамического программирования проблемы, оно может быть реализовано с использованием памяти O(number of subproblems).

В вашей конкретной проблеме «вычисления чисел Фибоначчи», если вы записываете простое решение динамического программирования:

Integer F(Integer n) { 
    if (n == 0 || n == 1) return 1; 
    if (memorized[n]) return memorized_value[n]; 
    memorized_value[n] = F(n - 1) + F(n - 2); 
    memorized[n] = true; 
    return memorized_value[n]; 
} 

он будет использовать O(number of subproblems) память. Но, как вы упомянули, анализируя повторение, вы можете найти более оптимальное решение, которое использует память O(1).

P.S. Повторяемость чисел Фибоначчи, которые вы упомянули, имеет n + 1 подзапросы. Обычно по подзадачам люди ссылаются на все значения f, которые необходимо вычислить для вычисления определенного значения f. Здесь вам нужно рассчитать f(0), f(1), f(2), ..., f(n), чтобы вычислить f(n).