动态规划--DAG（有向无环图）

1、矩形嵌套问题

问题描述：

• 设有n个矩形。
• 每个矩形由长宽两个整数a、b定义。
• 矩形X(a,b)能够容纳于Y(c,d)内当且仅当满足以下任一条件：一是a < c且b < d；二是b < c且a < d。
• 我们的任务是尽可能地选择一组这些矩形并将其排列成一列。
• 使得在排列中的每一个（除了最后一个）均能够被其后的每一个所包含。
• 若有多个解，则选取编号字典顺序最小的一组。

分析：

• 矩形间的可包含关系是一种典型的二元关系；这种二元关系可以通过构建相应的图模型来描述。如果一个矩形X能够完全包含另一个矩形Y，则可以在图中添加一条从X指向Y的有向边；该有向图不存在环路；换句话说，在这种模型中它是一个无环图（DAG）。我们的目标即是在这种DAG结构中找到最长路径；具体来说，在状态转移方程中：E代表所有允许的边集合；计算时的第一个步骤是确定当前节点的所有邻居节点。

    d(i)=max{d(j)+1|(i,j)∈E}

解决方法：

• 代码如下：第一步使用邻接矩阵将图存储在矩阵G中（在编写主程序之前需对程序进行测试与调试以确保建图过程无误），随后编写记忆化搜索算法，并将在初始化阶段将数组d的所有元素设为零.

 int dp(int i)

    
 {
    
     int &