使用迭代的动态规划问题
我花了很多时间学习如何使用迭代来实现/可视化动态规划问题，但我发现很难理解，我可以使用递归和回忆法实现同样的问题，但是与迭代相比，它是缓慢的。
有人能通过一个困难问题的例子或使用一些基本概念来解释同样的问题吗？如矩阵链乘法、最长回文子序列等。为了提高效率，我可以理解递归过程，然后回溯重叠子问题，但是我不知道如何使用迭代来完成同样的工作。
谢谢!
回答 2
Stack Overflow用户
发布于 2016-07-30 19:02:22
动态规划就是为了解决更大的问题而解决的子问题.递推法和迭代法的区别在于前者是自顶向下的，后者是自下而上的。换句话说，使用递归，你从你想要解决的大问题开始，把它分解成一个更小的子问题，在这个子问题上你重复这个过程，直到你到达你能解决的子问题。这有一个优势，你只需要解决那些绝对需要的子问题，并且使用回忆录来记住你所做的结果。自下而上的方法首先解决所有的子问题，使用表格来记住结果.如果我们没有做额外的工作来解决不需要的子问题，这是一个更好的方法。
对于一个简单的例子，让我们看一下斐波纳契序列。假设我们想计算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。我们正在进行一种迭代方法，因此我们将首先计算长度为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之间的所有位置，计算子问题。
希望我能帮上忙。
Stack Overflow用户
发布于 2016-08-03 23:10:40
递归的问题是大量需要推送/弹出的堆栈帧。这很快就会成为瓶颈。
Fibonacci级数可以用迭代DP计算，也可以用回溯递归计算。如果我们计算DP中的F( 100 )，我们只需要一个长度为100的数组，例如int[100]，这就是我们使用的内存的核心。我们计算数组的所有条目，预先填充f[0]和f[1]，因为它们被定义为1。每个值都取决于前两个值。
如果我们使用递归解决方案，我们从fib(100)开始，然后开始工作。从100到0的每个方法调用都被推到堆栈上，和检查它是否已回传。这些操作加在一起，迭代不会受到这两种情况的影响。在迭代(自下而上)中，我们已经知道前面的所有答案都是有效的。更大的影响可能是堆栈框架；给定更大的输入，您可能会得到一个StackOverflowException，因为在其他情况下，使用迭代的DP方法是微不足道的。
https://stackoverflow.com/questions/38532006
复制相似问题
腾讯云开发者
