目录简介经典问题最长上升子序列区间dp树形dp状压dp
简介
动态规划，dynamic programming，简称 dp，通过把原问题分解成更小的子问题来解决问题，适用于有重叠子问题和最优子结构的问题。重叠子问题是指某一个子问题的答案可能被多个更大的问题使用到，而最优子结构是指当更大的问题满足最优解时该子问题也满足这个解。
所以，当我们使用动态规划解决某一个状态的最优化问题时，往往需要用到之前的某些状态的结果，而之前的这些状态是在之前已经计算出最优值的，这和递推有很大的相似之处。不严格情况下往往都统称为动态规划。
解决动态规划问题最重要的两个东西是状态转移方程和边界条件。
经典问题
