算法-2018-12-24-打卡

• 算法导论之动态规划

1. 动态规划与分治算法相似，都是通过组合子问题的解来求解原问题。但是与分治算法存在一些区别：分治算法将原问题转化为互不相交的子问题，递归求解子问题，再将它们的解组合起来，最终求出原问题的解。与之相反，动态规划主要解决的是子问题存在重叠的情况，即不同的子问题具有公共的子问题（子问题的求解是递归进行的，将其划分为更小的子子问题）。这种情况下分治算法会做出许多存在重复的工作，反复求解公共的子问题。二对于动态规划而言，之求解一次并将其保存在一个表格里面，从而不必每一次都求解子子问题，避免了不必要的计算。
2. 动态规划方法通常用于求解最优化问题，最优化问题有很多可行的解，每一个解都有一个值，我们希望寻找具有最优值的解。最优值的解称呼为最优解。注意：最优值的解不一定是最优解，因为多各解都可能是最优值！！