使用迭代的動態規劃問題

Question

我花了很多時間學習使用迭代實現/可視化動態規劃問題，但我覺得很難理解，我可以通過使用遞歸實現memoization，但是在比較時速度很慢迭代。

有人可以解釋一個難題的例子或通過使用一些基本概念。像矩陣鏈增殖，最長的迴文子序列和其他。我可以理解遞歸過程，然後記憶重疊的子問題的效率，但我不明白如何使用迭代來做同樣的事情。

謝謝！

Answer 1

動態規劃就是要解決子問題，以解決更大的問題。遞歸方法和迭代方法之間的區別在於前者是自上而下的，而後者是自下而上的。換句話說，使用遞歸，你從你正在嘗試解決的大問題開始，並將其分解爲更小的子問題，在這個子問題上你重複這個過程，直到你達到可以解決的小問題。這有一個好處，你只需要解決絕對需要的子問題，並使用記憶來記住結果。自下而上的方法首先解決所有的子問題，使用製表記憶結果。如果我們不做額外的工作來解決不需要的子問題，這是一個更好的方法。

對於一個更簡單的例子，我們來看一下斐波那契數列。假設我們想計算F(101)。遞歸執行時，我們將從我們的大問題開始 - F(101)。爲此，我們注意到我們需要計算F(99)和F(100)。然後，對於F(99)，我們需要F(97)和F(98)。我們繼續下去，直到達到最小的可解子問題，即F(1)，並記錄結果。迭代地進行時，我們從最小的子問題F(1)開始，繼續向上，將結果保存在一個表中（所以本質上它只是一個從1到101的簡單循環）。

讓我們來看看您請求的矩陣鏈乘法問題。我們將從一個簡單的遞歸實現開始，然後是遞歸DP，最後是迭代DP。它將在C/C++湯中實現，但即使您對它們不是很熟悉，也應該能夠跟進。

/* Solve the problem recursively (naive) 

    p - matrix dimensions 
    n - size of p 
    i..j - state (sub-problem): range of parenthesis */ 
int solve_rn(int p[], int n, int i, int j) { 
    // A matrix multiplied by itself needs no operations 
    if (i == j) return 0; 

    // A minimal solution for this sub-problem, we 
    // initialize it with the maximal possible value 
    int min = std::numeric_limits<int>::max(); 

    // Recursively solve all the sub-problems 
    for (int k = i; k < j; ++k) { 
     int tmp = solve_rn(p, n, i, k) + solve_rn(p, n, k + 1, j) + p[i - 1] * p[k] * p[j]; 
     if (tmp < min) min = tmp; 
    } 

    // Return solution for this sub-problem 
    return min; 
} 

來計算結果，我們開始用大問題：

solve_rn(p, n, 1, n - 1) 

DP的關鍵是要記住所有的解決方案的子問題，而不是遺忘他們，所以我們不」不需要重新計算它們。這是微不足道的，使上述代碼進行一些調整，以實現這一目標：

/* Solve the problem recursively (DP) 

    p - matrix dimensions 
    n - size of p 
    i..j - state (sub-problem): range of parenthesis */ 
int solve_r(int p[], int n, int i, int j) { 
    /* We need to remember the results for state i..j. 
     This can be done in a matrix, which we call dp, 
     such that dp[i][j] is the best solution for the 
     state i..j. We initialize everything to 0 first. 

     static keyword here is just a C/C++ thing for keeping 
     the matrix between function calls, you can also either 
     make it global or pass it as a parameter each time. 

     MAXN is here too because the array size when doing it like 
     this has to be a constant in C/C++. I set it to 100 here. 
     But you can do it some other way if you don't like it. */ 
    static int dp[MAXN][MAXN] = {{0}}; 

    /* A matrix multiplied by itself has 0 operations, so we 
     can just return 0. Also, if we already computed the result 
     for this state, just return that. */ 
    if (i == j) return 0; 
    else if (dp[i][j] != 0) return dp[i][j]; 

    // A minimal solution for this sub-problem, we 
    // initialize it with the maximal possible value 
    dp[i][j] = std::numeric_limits<int>::max(); 

    // Recursively solve all the sub-problems 
    for (int k = i; k < j; ++k) { 
     int tmp = solve_r(p, n, i, k) + solve_r(p, n, k + 1, j) + p[i - 1] * p[k] * p[j]; 
     if (tmp < dp[i][j]) dp[i][j] = tmp; 
    } 

    // Return solution for this sub-problem 
    return dp[i][j];; 
} 

我們先從大的問題，以及：

solve_r(p, n, 1, n - 1) 

迭代的解決方案是唯一的，好了，遍歷所有各州而不是從頂部開始，：

/* Solve the problem iteratively 

    p - matrix dimensions 
    n - size of p 

    We don't need to pass state, because we iterate the states. */ 
int solve_i(int p[], int n) { 
    // But we do need our table, just like before 
    static int dp[MAXN][MAXN]; 

    // Multiplying a matrix by itself needs no operations 
    for (int i = 1; i < n; ++i) 
     dp[i][i] = 0; 

    // L represents the length of the chain. We go from smallest, to 
    // biggest. Made L capital to distinguish letter l from number 1 
    for (int L = 2; L < n; ++L) { 
     // This double loop goes through all the states in the current 
     // chain length. 
     for (int i = 1; i <= n - L + 1; ++i) { 
      int j = i + L - 1; 
      dp[i][j] = std::numeric_limits<int>::max(); 

      for (int k = i; k <= j - 1; ++k) { 
       int tmp = dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j]; 
       if (tmp < dp[i][j]) 
        dp[i][j] = tmp; 
      } 
     } 
    } 

    // Return the result of the biggest problem 
    return dp[1][n-1]; 
} 

來計算結果，只是把它：

solve_i(p, n) 

---

在最後一個例子的循環計數器的說明：

比方說，我們需要優化的4個矩陣乘法：A B C D。我們正在做一個迭代方法，所以我們將首先計算長度爲2的鏈：(A B) C D,A (B C) D和A B (C D)。然後是三條鏈：(A B C) D和A (B C D)。這就是L,i和j。

L表示鏈長度時，它從2進入n - 1（n是在這種情況下4，所以這是3）。

i和j代表鏈條的起始和結束位置。如果L = 2，i去從1到3，並j去從2到4：

(A B) C D  A (B C) D  A B (C D) 
^^   ^^   ^^ 
i j    i j    i j 

如果L = 3，i去從1到2，並j從3到4雲：

(A B C) D  A (B C D) 
^ ^  ^^
i j   i j 

所以一般來說，i從1到n - L + 1和j是i + L - 1。

現在，讓我們繼續假設我們處於(A B C) D的步驟。我們現在需要考慮子問題（已計算的）：((A B) C) D和(A (B C)) D。這就是k的用途。它通過i和j之間的所有位置並計算子問題。

我希望我能幫上忙。

Answer 2

遞歸的問題是需要推送/彈出的堆棧幀的數量很多。這可能很快成爲瓶頸。

斐波那契數列可以通過迭代DP或帶記憶的遞歸來計算。如果我們計算DP中的F（100），我們需要的是一個長度爲100的陣列，例如int[100]這就是我們用過的內存的膽量。我們計算預填充陣列f[0]和f[1]的所有條目，因爲它們被定義爲1。每個值都取決於前兩個值。

如果我們使用遞歸解決方案，我們從fib(100)開始，然後開始工作。從100到0的每個方法調用都會被壓入堆棧，如果它被記憶，則會檢查和。這些操作加起來並且迭代不會受到這兩者之一的影響。在迭代中（自下而上），我們已經知道所有以前的答案都是有效的。更大的影響可能是堆棧幀;並給出更大的輸入，你可能會得到一個StackOverflowException用於迭代DP方法的其他細節。