动态规划的状态设计有许多值得探讨的内容。本文会从基本模型讲起，拓展到一些复杂的内容。

之前的 DP 都是在线性结构上进行的，实际上 DP 还可以在树上或者 DAG 上进行。本文将对这些内容进行简单的介绍。

在 NOIP 范围内需要掌握的较难 DP 包括：状压 DP、单调队列优化 DP 和倍增优化 DP。

区间 DP 是线性 DP 的一种特殊形式，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。高维 DP 则是线性 DP 的扩展，大部分是从一条链扩展为了二维结构。

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20 世纪 50 年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。所以动态规划不仅在 OI 中应用广泛，在生活实际同样应用广泛。本文将引导你学习简单的动态规划。

背包是 DP 中一类重要而特殊的模型。本文将引导你学习各类背包。