是自下而上動態規劃遞歸？

在這種方法中，計算較小的子問題並緩存結果，然後計算較大的子問題，爲此我們使用緩存早期計算值的表中已計算的較小子問題的優化值。那麼，這種方法是遞歸的還是迭代的？是自下而上動態規劃遞歸？

2017-01-10 Deba

也沒有。 DP只是一種算法技術;它並不意味着實際的實現。邏輯是遞歸的（通過解決縮小的相同問題來解決更大的問題），如果這就是你的意思？ – Paul

我們在動態規劃中使用的方法實際上是inductive。可以將建設性歸納證明轉換爲遞歸算法或迭代算法。這只是品味的問題。例如。 memoization是一個遞歸實現，而對於每個memoized算法都有一個迭代的方法。

簡單的例子是斐波納契數。我們可以把它寫迭代：

Fib (n) 
{ 
    F_1=F_2=1; 
    For i =3..n 
     F_i = F_i-1 + F_i-2; 
    Return F_n; 
}

一個可以遞歸寫：

Define array F of size n; 
    F [1]=F [2]=1; 
    Fib (n) 
    { 
     If (F [n-1]==0) 
      F [n-1] = Fib (n-1); 

     If (F [n-2]==0) 
      F [n-2] = Fib (n-2); 
    F [n]= F[n-2]+F [n-1]; 
    Return F[n]; 
    }

他們兩個都是動態編程和他們有相同的順序。在某些情況下，遞歸更容易。在某些情況下，迭代速度更快。

來源

2017-01-10 22:34:21

我認爲這是一個很好的解釋。還有一點：有些編程語言不直接支持遞歸調用，所以直接的遞歸實現是不可能的。此外，顯然大多數人認爲各自的歸納公式表現出對問題的「更好理解」。我聽說了「評估順序」很重要的論點，因爲「首先需要評估基礎值」 - 然而，遞歸實現中也是如此。 – Codor

我不只是在談論動態規劃，而是專門討論它的兩種方法之一：自下而上的方法。爲什麼我認爲自下而上的方法具有迭代性（而不是遞歸），還有遞歸的另一個特點：我們從要解決的主要問題開始，在每次遞歸之後，我們向基礎條件移動一步。但是，如果採用這種自下而上的方法，我們將從基礎條件開始，緩存結果並使用它們來評估即將到來的結果。那麼它不是遞歸的而是迭代的？ – Deba

@Deba，正如我所說，它基本上是歸納性的。可以通過遞歸方法來處理歸納：通過將其大小減小到基本情況來解決最大的情況，這裏基本情況是歸納的小實例或基本情況。另一個可以自下而上的方法：基本解決問題，我們知道如何解決更大的實例，解決更大的實例。所以在這種情況下，遞歸和自下而上的方法只是實現歸納的工具。也許更自然的說它是自下而上的，但這只是品味的問題。 –

是自下而上動態規劃遞歸？

回答

相關問題