在枚举一文中，我们提出状态空间的概念。状态空间需要自己设计，且没有固定的范式。不过对于动态规划dp来说，其状态空间的结点可以用集合一一对应，这为我们分析dp问题提供了方法。
具体来说，如果我们将若干种可能情况看作集合，将这些可能情况的最优值看作集合的属性。那么在dp问题中，状态的定义对应于集合的属性，状态的转移对应于集合的划分。大一级集合被划分为小一级集合，大一级集合的属性由小一级集合的属性直接推导出来。而最小的原子集合的属性可以直接求出，dp问题的答案又可以由若干个大集合的属性求出。从而dp问题就可以用一种自底向上的方法，从原子集合开始层层推导得出答案。
可以看出，dp问题的状态空间是非欧空间（树或森林）。
一个问题要能够使用dp求解必须具备三个性质：子问题重叠性、无后效性、最优子结构性。
dp的集合划分最终会形成一个非欧状态空间（树或森林），其中存在大量重复结点（每个结点对应一次计算），从而导致大量重复计算。dp效率较高的原因在于，通过记忆化的方法，重复的结点只计算第一次，再次使用时可以直接返回已经计算好的结果，从而避免重复计算。换言之，如果一个问题没有子问题重叠性，那么dp也就失去了优化作用。
首先我们知道，过去的状态&决策决定了当前阶段的状态，那么，无后效性指的是：当前的状态确定之后，未来的决策&状态取决于且只取决于当前的状态。 无后效性包含两层含义： 一是只有当前的状态在影响着未来的决策&状态，过去的状态&决策不会影响未来的决策&状态（即“只取决于”）； 二是未来的决策&状态不会影响当前的状态（即“取决于”，不能反推）。 换句话说，无后效性描述的是一种当前对未来的单向唯一决定关系，既不会过去影响将来（唯一），也不会将来改变当前（单向）。
有了无后效性，我们可以放心地使用已知集合的属性求解后面更大集合的属性，既不用担心集合的扩大导致已知集合的属性发生改变，也不用担心更大集合属性的求解会用到除了已知集合属性之外的更多信息。
最优子结构性是指：子问题的最优解能推出更大问题的最优解，更大问题的最优解包含其子问题的最优解。
综合来看，无后效性和最优子结构性要保证的是：既不能让集合的扩大导致已知集合的最优值发生改变，也不能让更大集合属性的求解要用到除了已知集合最优值之外的更多信息。
dp的求解策略总结起来就是：记忆化搜索。它与非欧状态空间对结点的暴力搜索类似，但是另辟空间记录已经求出的结点的值，重复的结点只计算第一次，后面再用到时直接返回结果。在枚举一文中我们讨论过对状态空间的枚举（枚举结点或枚举路径，一般是自顶向下），而记忆化搜索只是搜索结点，并且都是自底向上。
非欧状态空间对结点的暴力搜索有两种方式：DFS和BFS，那么理论上讲，dp的记忆化搜索应该要有两种方式：记忆化的自底向上DFS和记忆化的自底向上BFS。自底向上DFS没有问题，但对于自底向上BFS，我们没有办法先计算子结点，再计算父结点，所以自底向上BFS不能用了。
不过dp有与自底向上BFS十分相近的解法（都是通过循环实现，方向都是自底向上）：递推。递推时，先将所有原子集合属性初始化，然后按照递推公式层层向上推导出所有集合属性，最后计算问题的答案（由若干个大集合的属性求出）。根据子问题重叠性我们知道，dp的状态空间有大量的重复结点，递推将这些重复结点合并为一个，从而达到只计算一次的目的。所以，递推的状态空间不再是树或森林，而是类似树或森林的结构（可能存在某些结点有多个父结点，所以并不是严格的树或森林）。
\[\text{动态规划dp} \left\{ \begin{aligned} &\text{递归解法：记忆化的自底向上DFS，不改变状态空间}\\ &\text{循环解法：自底向上递推，合并状态空间的重复结点} \end{aligned} \right.\]