1. 简介

通过子问题最优解推出当前最优解

初始化

• 初始化为0
• 初始化为INF
• 初始化为-INF

  状态迁移方程

  从子问题推到后续问题答案的方程，如
  状态迁移需满足无后效性，即当前推导的状态，不会被之后的状态影响。

2. DP模型

2.1 DAG图

嵌套矩形问题。有 n 个矩形，每个矩形可以用两个整数 a、b 描述，表示他的长和宽。矩形 X(a,b) 可以嵌套在 Y(c,d) 中，当且仅当 a<b, b<d 或者 b<c, a<d。你的任务是选出尽量多的矩形排成一行，使得除了最后一个之外，每一个矩形都可以嵌套在下一个矩形中。

结点与结点之间存在一个典型的二元关系，二元关系可以用图来建模。举个例子：

如果这个关系满足如下条件，那么这个图就是 DAG 图。

这里的>只是举个例子，其他符号也行。

对于这类 DAG 图问题，可以使用如下状态转移方程

可以使用记忆化搜索或者递归方式求解，记忆化有个缺陷就是多个解就要多个函数。

a: t为时间、i 和 j 为车站, dp为 t 时刻 i 车站最小等待时间，C为从 j 坐火车到 i 的时间

b: 把一个人从起点到终点来回旅行，等价替换为两个人从起点一起走到终点…
令 dp(i, j) 为已经访问过max(i,j)所有结点后，一个人在 i ，一个人在 j，此时到终点两人还需要走的距离

边界条件为 dp(n-1, j) ，这个时候只要令人分别走到终点即可。

2.2 多阶段决策

简单地说，每做一次决策就可以得到解的一部分，当所有决策做完之后，完整的解就“浮出水面”了。

2.3 线性动态规划

问题分类：

2.4 区间动态规划

2.5 树与图上的动态规划

2.6 状态压缩动态规划

2.7 暂未分类

Reference

• 背包九讲