对一个初高中甚至大学都没有接触计算机算法竞赛的我来说，动态规划还是需要用心才能理解的，所以要总结一下。该文章某些部分取自刘汝佳的《算法竞赛入门经典（第2版）》
- 理解状态和状态转移方程
- 理解最优子结构和重叠子问题
- 熟练运用递推法和记忆化搜索求解数字三角形问题
- 熟悉DAG上动态规划的常见思路、两种状态定义方法和刷表法
- 掌握记忆化搜索在实现方面的注意事项
- 掌握记忆化搜素和递推中输出方案的方法
- 掌握递推中滚动数组的使用方法
- 熟练解决经典动态规划问题
相关概念
- 最小子结构：问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解。
相关题型
- 背包DP
- 区间DP
- 线性DP
- DAG上的DP
- 树形DP
- 状压DP
- 数位DP
- 插头DP
- 计数DP
- 动态DP
- 递推DP：矩阵快速幂
- 概率DP
- 博弈DP