动态规划(Dynamic Programming):简称 DP,是一种求解多阶段决策过程最优化问题的方法。在动态规划中,通过把原问题分解为相对简单的子问题,先求解子问题,再由子问题的解而得到原问题的解。
思想
动态规划的核心思想:
- 把「原问题」分解为「若干个重叠的子问题」,每个子问题的求解过程都构成一个 「阶段」。在完成一个阶段的计算之后,动态规划方法才会执行下一个阶段的计算。
- 在求解子问题的过程中,按照「自顶向下的记忆化搜索方法」或者「自底向上的递推方法」求解出「子问题的解」,把结果存储在表格中,当需要再次求解此子问题时,直接从表格中查询该子问题的解,从而避免了大量的重复计算。