动态规划DP算法详解

动态规划DP算法详解

定义

动态规划(dynamic programing)和分治法类似,都是通过组合子问题的解来求解原问题的解。(在经典排序算法中的二路归并排序和快速排序都用到了分而治之的思想-分治法)。

分治法是将原问题划分为没有交集,相互独立的子问题,并分别求解后再进行合并,求出原问题的解。

动态规划应用于子问题重叠的情况,即不同的子问题具有公共的子子问题。分治法会做许多不必要的工作,它会反复地求解那些公共子问题。动态规划算法对每个子问题只求解一次,将其解保存在一个表格中,从而无需每次求解一个子子问题时都需要重新计算。

算法成长之路leetcode9-10