使用迭代的动态编程问题

Question

我花了很多时间来学习使用迭代实现/可视化动态编程问题,但我发现它很难理解,我可以使用memoization的递归实现相同的但是与迭代相比它很慢.

有人可以通过硬问题的例子或使用一些基本概念来解释相同的问题.像矩阵链乘法,最长的回文子序列和其他.我可以理解递归过程,然后记住重叠的子问题以提高效率,但我无法理解如何使用迭代来做同样的事情.

谢谢!

Answer 1

动态编程就是解决子问题以解决更大问题.递归方法和迭代方法之间的区别在于前者是自上而下,后者是自下而上.换句话说,使用递归,你可以从你想要解决的大问题开始,然后将其分解为更小的子问题,在这个问题上你重复这个过程,直到你达到子问题这么小,你可以解决.这样做的好处是,您只需解决绝对需要的子问题,并使用memoization记住结果.自下而上的方法首先解决所有子问题,使用制表来记住结果.如果我们没有做额外的工作来解决不需要的子问题,这是一种更好的方法.

更简单的例子,让我们看一下Fibonacci序列.说我们想要计算F(101).当递归地进行时,我们将从我们的大问题开始 - F(101).为此,我们注意到我们需要计算F(99)和F(100).然后,因为F(99)我们需要F(97)和F(98).我们继续,直到我们达到最小的可解决的子问题,即F(1)记住结果.当迭代地进行时,我们从最小的子问题开始,F(1)并继续一直向上,将结果保存在表中(因此在这种情况下,它实际上只是一个简单的for循环,从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.我们正在做一个迭代的方法,所以我们首先计算与两个长链:(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与计算子问题.

我希望我帮忙.