動態規劃：真或假

我有一個關於動態規劃的概念疑問：動態規劃：真或假

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)

這裏有兩個子問題，所需的空間如果輸入爲n，則至少爲O（n）。對不對？

但是，答案是錯誤的。

有人可以解釋這一點嗎？

來源

2015-11-05 Jay Patel

並非所有的動態編程問題都需要你使用額外的空間，而任何自上而下的自上而下都可以轉換爲自下而上以防止堆棧溢出。 –

@ C.B。在最壞的情況下，底層/自上而下不會在大O符號方面改變空間複雜性。 – amit

答案確實是錯誤的。

例如，在你的斐波那契數列，您可以使用帶有O（1）空間動態規劃，通過記住只有最後2個數字：

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

這是一種常見的做法，你不需要所有較小的子問題都可以解決更大的問題，並且可以丟棄其中的大部分並節省一些空間。

來源

2015-11-05 21:24:27 amit

正確或錯誤：如果動態規劃解決方案設置正確，即遞推方程是正確的，並且每個唯一的子問題只解決一次（記憶），則所得到的算法將始終在多項式時間內找到最優解。 –

如果您使用自下而上的DP實施斐波納契計算，則可以丟棄您不需要的早期結果。這是一個例子：

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

這個例子說明，你只需要記住數組中的最後兩個元素。

來源

2015-11-05 21:24:36 stanleyli

此聲明不正確。但它幾乎是正確的。

一般動態規劃解決方案需要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)。

來源

2015-11-06 00:42:27

動態規劃：真或假

回答

相關問題