动态编程和分支定界和有什么区别？

Question

我只知道通过分支定界，可以减少获取解决方案的过程，但这仅对具有解决方案空间树的问题有所帮助。

Answer 1

动态编程

动态编程（通常称为DP）是解决特定类型问题的一种非常强大的技术。它需要非常优雅的方法表述和简单的思考，并且编码部分非常容易。
这个想法很简单，如果用给定的输入解决了问题，则将结果保存起来以备将来参考，以免再次解决相同的问题。不久，“记住您的过去”。

如果可以将给定的问题分解为较小的子问题，然后将这些较小的子问题又分解为较小的子问题，并且在此过程中，如果您观察到一些重叠的子问题，那么这对于DP有很大的提示。而且，子问题的最优解有助于给定问题的最优解（称为最优子结构属性）。

有两种方法可以做到这一点。

1.) Top-Down : Start solving the given problem by breaking it down. If you see that the problem has been solved already, then just return the saved answer. If it has not been solved, solve it and save the answer. This is usually easy to think of and very intuitive. This is referred to as Memoization.
2.) Bottom-Up : Analyze the problem and see the order in which the sub-problems are solved and start solving from the trivial subproblem, up towards the given problem. In this process, it is guaranteed that the subproblems are solved before solving the problem. This is referred to as Dynamic Programming.

分支定界

• 一个分支定界算法由候选解决方案的系统枚举借助于状态空间搜索：该组候选解被认为是与全套在根部形成根树。
  
• 该算法探索该树的分支，这些分支代表解决方案集的子集。在枚举分支的候选解决方案之前，先根据最佳解决方案上的估计上下限检查分支，如果该分支无法产生比算法到目前为止找到的最佳解决方案更好的解决方案，则将其丢弃。
  

有关分支和绑定的更多信息，请参考以下链接：

http://www.cs.umsl.edu/~sanjiv/classes/cs5130/lectures/bb.pdf

Answer 2

动态规划需要递归结构（又名 CRLS 中的最优子结构）。也就是说，在给定状态下，人们可以根据部分解决方案来描述最佳决策。

分支定界更通用，用于通过解空间的隐式枚举来解决更困难的问题。