动态规划是解决多阶段决策优化问题的一种方法。动态规划高效的关键在于减少了“冗余”，即减少了不必要或重复计算的部分。动态规划在自底向上的求解过程中，记录子问题的求解结果，避免重复求解子问题，提高了效率。
动态规划的时间复杂度计算抽象公式：时间复杂度=状态总数×每个状态的决策数×每次状态转移所需的时间
可以从三个方面进行动态规划优化：状态总数、每个状态的决策数和每次状态转移所需的时间。
（1）减少状态总数的基本策略包括修改状态表示（状态压缩、倍增优化）、选择适当的DP方向（双向DP）等。
（2）减少状态的决策数，最常见的是利用最优决策单调性进行四边不等式优化、剪枝优化。
（3）减少状态转移所需的时间，可采用预处理、合适的计算方法和数据结构优化。