使用迭代的动态规划问题

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方法的其他细节。