定义

动态规划（Dynamic programming）是用一种在数学，计算机科学和经济学中使用的，通过把愿问题分解为相对简单的子问题的方法求解复杂问题的方法。
动态规划常常适用于有重叠子问题和最优子结构性质的问题。动态规划方法的耗时少于朴素算法。

什么是最优子结构？

当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。

什么是重叠子问题？

在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每个子问题只借一次，而后将其保存在一个表格中，在以后尽可能多🉐️利用这些子问题的解。