回到跟踪和动态规划的区别 [英] difference between back tracking and Dynamic programming

问题描述

我听到了动态规划和后跟踪之间的唯一区别是DP允许重叠的子问题。 （FIB（n）的FIB =（N-1）+ FIB（N-2））。这样对吗 ？是否还有其他的区别？此外，我想知道使用这些技术解决了一些常见的问题。

I heard the only difference between dynamic programming and back tracking is DP allows overlapping of sub problems. (fib(n) = fib(n-1)+ fib (n-2)). Is it right ? Are there any other differences ? Also I would like know some common problems solved using these techniques.

推荐答案

有动态规划方法有两个典型的实现：底部到顶部和顶至底。

There are two typical implementations of Dynamic Programming approach: bottom-to-top and top-to-bottom.

最常见到低端的动态规划的是没有比其他普通的递归的，增强记忆中间的子问题的解决方案。当一个给定的子问题出现第二（第三，第四......）的时间，它不是从头解决，但代替previously存储溶液用于马上。这种技术的名义下知的记忆化的（没有'R'之前'我'）。

Top-to-bottom Dynamic Programming is nothing else than ordinary recursion, enhanced with memorizing the solutions for intermediate sub-problems. When a given sub-problem arises second (third, fourth...) time, it is not solved from scratch, but instead the previously memorized solution is used right away. This technique is known under the name memoization (no 'r' before 'i').

这其实是与Fibonacci序列的例子应该做以说明。只需使用递推公式为Fibonacci序列，但建 FIB（我）值沿途的表，你会得到一个顶至底DP算法对于这个问题（所以，举例来说，如果你需要计算 FIB（5）第二次，你得到它从表中，而不是重新计算的话）。

This is actually what your example with Fibonacci sequence is supposed to illustrate. Just use the recursive formula for Fibonacci sequence, but build the table of fib(i) values along the way, and you get a Top-to-bottom DP algorithm for this problem (so that, for example, if you need to calculate fib(5) second time, you get it from the table instead of calculating it again).

在底部至顶部的动态规划的这种方法也是基于存储子解决方案中的存储器，但是它们都解决了以不同的顺序（从较小到较大），并且将所得的一般该算法的结构不是递归。 LCS算法是一个典型的底部到顶部的DP的例子。

In Bottom-to-top Dynamic Programming the approach is also based on storing sub-solutions in memory, but they are solved in a different order (from smaller to bigger), and the resultant general structure of the algorithm is not recursive. LCS algorithm is a classic Bottom-to-top DP example.

底部至顶部的DP的算法通常更有效，但它们通常是硬的（有时是不可能的），以建立，因为它并不总是容易predict说明您将原始的子问题，以需要解决整个原始问题，并且其路径有从小型子问题采取以获得以最有效的方式最终溶液

Bottom-to-top DP algorithms are usually more efficient, but they are generally harder (and sometimes impossible) to build, since it is not always easy to predict which primitive sub-problems you are going to need to solve the whole original problem, and which path you have to take from small sub-problems to get to the final solution in the most efficient way.

这篇关于回到跟踪和动态规划的区别的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！