使用迭代的动态编程问题

动态编程就是为了解决更大的问题而解决子问题。递归方法和迭代方法的区别在于,前者是自顶向下的,而后者是自下而上的。换言之,使用递归,您可以从要解决的大问题开始,然后将其分解为更小的子问题,在这些子问题上重复此过程,直到找到可以解决的小问题为止。这有一个优点,你只需要解决绝对需要的子问题,并使用记忆来记住结果。自下而上的方法首先解决所有子问题,使用表格来记住结果。如果我们不做额外的工作来解决不需要的子问题,这是一个更好的方法。

举个简单的例子,让我们看看斐波那契序列。假设我们想计算 F(101) .当递归执行时,我们将从我们的大问题开始- F(101) 为此,我们注意到需要计算 F(99) 和 F(100) 然后,对于 F(99) 我们需要 F(97) 和 F(98) 。我们继续下去,直到找到最小的可解子问题,即 F(1) ,并将结果存储起来。迭代时,我们从最小的子问题开始, F(1) 并一直向上,将结果保存在一个表中(因此在本例中,它实际上只是一个从1到101的简单for循环)。

让我们看看您所要求的矩阵链乘法问题。我们将从简单的递归实现开始,然后是递归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 ).

和 j 表示链的开始和结束位置。万一 L = 2 , 我 来自 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 , 我 来自 1. 到 2. 和 j 来自 3. 到 4. :

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

一般来说, 我 来自 1. 到 n - L + 1 和 j 是 i + L - 1 .

现在,让我们继续进行算法,假设我们处于 。我们现在需要考虑子问题(已经计算): ((A B) C) D 和 (A (B C)) D .这就是 k 是的。它会穿过所有位置 我 和 j 并计算子问题。

我希望我能帮上忙。

递归的问题是需要推/弹出的堆栈帧数量太多。这可能很快成为瓶颈。

斐波那契级数可以用迭代DP或递归记忆法计算。如果我们计算DP中的F(100),我们所需要的只是一个长度为100的数组,例如。 int[100] 这就是我们过去的记忆。我们计算数组预填充的所有条目 f[0] 和 f[1] 定义为 1 .并且每个值仅取决于前两个值。

如果我们使用递归解决方案,我们从 fib(100) 和 检查它是否已被记忆。这些操作加起来,迭代不会受到这些操作的影响。在迭代(自下而上)中,我们已经知道前面的所有答案都是有效的。更大的影响可能是堆栈帧;如果输入量较大,您可能会得到 StackOverflowException 对于迭代DP方法来说是微不足道的。