动态规划递归或迭代
动态规划可以以“迭代”和“递归”方式应用吗？还是只应用其中一种方式是一种好的做法？
Can Dynamic Programming be applied in an "iterative" and a "recursive" way or is it good practice to apply it only one of the ways?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
是的，DP 可以应用于两者。
从这里开始：http://en.wikipedia.org/wiki/Dynamic_programming
然后你有动态编程：从新手到高级 和动态规划教程
对于第一个教程，您将找到以下链接TopCoder.com 练习问题（每个问题都有一个 社论 解释解决方案背后的想法。
Yes, DP can be applied to both.
Start here: http://en.wikipedia.org/wiki/Dynamic_programming
Then you have Dynamic Programming: From novice to advanced and A Tutorial on Dynamic Programming
For the first tutorial, you will find links to TopCoder.com problems for practice (each of these problems have also an Editorial explaining the idea behind the solution.
动态编程（在许多情况下）可以被视为反向实现的递归解决方案。
通常，在递归中，您将计算
x(n+1) = f(x(n))，其中包含n=0的某个停止条件（或其他值） ）。在许多情况下，函数
f是某个最小/最大函数，但并非必须如此。此外，该函数不必采用单个变量。
动态规划可以通过计算
f(0)、然后f(1)、然后f(2)等来解决这个问题。一个变量，通常会有一些自然顺序来计算函数。
动态规划可以解决的一个例子：
给您 3 个高尔夫球杆。每个高尔夫球杆可以将高尔夫球向前发送 x 个单位的距离（例如，24、37 和 54 个单位）。问题是：你能击中 200 个单位外的洞吗？如果可以的话，您需要的最少拍摄次数是多少？
递归解决方案类似于：
这将允许一个简单的实现，其中如果 n 为 0，函数
shot(n)返回 0，如果 n 小于 0，则返回某个巨大的数字，以及上面的表达式否则。然而，对于较大的 n 值，您将在上述表达式的不同分支中一次又一次地得到相同的值。在这种情况下，最好从 0 开始计算
shots(0)、shots(1)、shots(2)等。这将是该问题的“动态编程”解决方案 - 使用线性时间和常数空间而不是指数时间（遍历三向树）和线性空间（对于调用堆栈）。Dynamic programming can be seen (in many cases) as a recursive solution implemented in reverse.
Normally, in a recursion, you would calculate
x(n+1) = f(x(n))with some stop condition forn=0(or some other value).In many cases the function
fis some min/max function, but it doesn't have to be.Also, the function doesn't have to take a single variable.
Dynamic programming would solve this problem by calculating
f(0), thenf(1), thenf(2)etc.With more than one variable, there would normally be some natural order to calculate the function.
An example that dynamic programming can solve:
You are given 3 golf clubs. Each golf club can send a golf ball x units of distance forward (for example, 24, 37 and 54 units). The question is: can you hit a hole that is exactly 200 units away? And if you can, what's the minimum number of shots you need.
The recursive solution would be something like:
This would allow a trivial implementation, where the function
shot(n)returns 0 if n is 0, some huge number if n is less than 0, and the expression above otherwise.However, for large values of n you will hit the same values again and again, from different branches of the expression above. In that case, it's better just to start from 0 and calculate
shots(0),shots(1),shots(2)etc. This would be the "dynamic programming" solution to this problem - using linear time and constant space instead of exponential time (traversing a 3-way tree) and linear space at best (for the call stack).