动态规划（dynamic programming）与分治方法相似，都是通过组合子问题的解来求解原问题（在这里，“programming”指的是一种表格法，并非编写计算机程序）。分治方法将问题划分为互不相交的子问题，递归的求解子问题，再将它们的解组合起来，求出原问题的解。动态规划应用于子问题的解重叠的情况，即不同的子问题具有公共的子子问题。在这种情况下，分治算法会做许多不必要的工作，它会反复地求解那些公共子问题。而动态规划算法对每个子子问题只求解一次，将其保存在一个表格中，从而无需每次求解一个子子问题的解时都重新计算，避免了不必要的计算工作。
12
2019
03
动态规划
发布:hanyeah | 分类:算法 | 评论:0 | 浏览: