递归可以动态编程吗？ [英] Can recursion be dynamic programming?
问题描述
有人要求我使用动态编程来解决问题。我对构成动态编程的观点有好有坏。我认为这需要一种自下而上的方法，首先解决最小的问题。
I was asked to use dynamic programming to solve a problem. I have mixed notes on what constitutes dynamic programming. I believe it requires a "bottom-up" approach, where smallest problems are solved first.
我有一个矛盾的信息是，某些东西是否可以动态编程相同的子问题可以多次解决，这在递归中很常见。
One thing I have contradicting information on, is whether something can be dynamic programming if the same subproblems are solved more than once, as is often the case in recursion.
例如。对于斐波那契，我可以有一个递归算法：
For instance. For Fibonacci, I can have a recursive algorithm:
RecursiveFibonacci(n)
if (n=1 or n=2)
return 1
else
return RecursiveFibonacci(n-1) + RecursiveFibonacci(n-2)
在这种情况下，相同的子问题可能会一遍又一遍地解决。这是否使它成为 not 动态编程？也就是说，如果我想进行动态编程，我将必须避免解决子问题，例如使用长度为n的数组并将解决方案存储到每个子问题（该数组的第一个索引为1，1 ，2、3、5、8、13、21）？
In this situation, the same sub-problems may be solved over-and-over again. Does this render it is not dynamic programming? That is, if I wanted dynamic programming, would I have to avoid resolving subproblems, such as using an array of length n and storing the solution to each subproblem (the first indices of the array are 1, 1, 2, 3, 5, 8, 13, 21)?
Fibonacci(n)
F1 = 1
F2 = 1
for i=3 to n
Fi=Fi-1 + Fi-2
return Fn
推荐答案
动态程序通常可以用递归公式简单地描述。
Dynamic programs can usually be succinctly described with recursive formulas.
但是，如果使用简单的递归计算机程序来实现它们，则由于您提出的原因，它们通常效率不高：重复相同的计算。尽管斐波那契不是动态程序，但它是重复计算的一个示例。
But if you implement them with simple recursive computer programs, these are often inefficient for exactly the reason you raise: the same computation is repeated. Fibonacci is a example of repeated computation, though it is not a dynamic program.
有两种避免重复的方法。
There are two approaches to avoiding the repetition.
-
记忆。这里的想法是将为递归函数的每个参数集计算出的答案缓存起来，并在缓存的值存在时返回。
Memoization. The idea here is to cache the answer computed for each set of arguments to the recursive function and return the cached value when it exists.
自下而上的表。在这里，您展开递归，以便将小于i的结果合并到i的结果。通常将其描述为填充表格，其中的级别为行。
Bottom-up table. Here you "unwind" the recursion so that results at levels less than i are combined to the result at level i. This is usually depicted as filling in a table, where the levels are rows.
其中一种方法对于任何DP算法都暗含。如果重复计算，则该算法不是DP。因此，您的问题的答案是是。
举个例子……让我们尝试一下在您有硬币的情况下改变c美分的问题值v_1，v_2，... v_n，使用最小数目的硬币。
So an example... Let's try the problem of making change of c cents given you have coins with values v_1, v_2, ... v_n, using a minimum number of coins.
让N（c）是赚取c分所需的最小硬币数目。那么一种递归公式是
Let N(c) be the minimum number of coins needed to make c cents. Then one recursive formulation is
N(c) = 1 + min_{i = 1..n} N(c - v_i)
基本情况是N（0）= 0和N（k）= inf，k < 0。
The base cases are N(0)=0 and N(k)=inf for k<0.
要记住这一点，只需要将c映射到N（c）的哈希表即可。
To memoize this requires just a hash table mapping c to N(c).
在这种情况下，表只有一个维，很容易填写。假设我们有硬币，其值分别为1、3、5，然后是N表以
In this case the "table" has only one dimension, which is easy to fill in. Say we have coins with values 1, 3, 5, then the N table starts with
- N（0）= 0（初始条件）开始。
- N（1）= 1 + min（N（1-1），N（1-3），N（1-5）= 1 + min（0，inf，inf ）= 1
- N（2）= 1 + min（N（2-1），N（2-3），N（2-5）= 1 + min（1， inf，inf）= 2
- N（3）= 1 +分钟（N（3-1），N（3-3），N（3-5）= 1 +分钟（2，0，inf）= 1
- N(0) = 0, the initial condition.
- N(1) = 1 + min(N(1-1), N(1-3), N(1-5) = 1 + min(0, inf, inf) = 1
- N(2) = 1 + min(N(2-1), N(2-3), N(2-5) = 1 + min(1, inf, inf) = 2
- N(3) = 1 + min(N(3-1), N(3-3), N(3-5) = 1 + min(2, 0, inf) = 1
您知道了，您始终可以从N（d）计算N（c） ，d< c就是这种方式。
You get the idea. You can always compute N(c) from N(d), d < c in this manner.
在这种情况下，您只需要记住最后5个值，因为那是最大的硬币价值。大多数DP相似。
In this case, you need only remember the last 5 values because that's the biggest coin value. Most DPs are similar. Only a few rows of the table are needed to get the next one.
对于递归表达式中的k个独立变量，表是k维的。
The table is k-dimensional for k independent variables in the recursive expression.
这篇关于递归可以动态编程吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
