引言：

DAG：有向无环图。

DAG是学习动态规划的基础，很多问题都可以直接转化为DAG上的最长路、最短路或路径计数问题。

两个经典的DAG模型，嵌套矩形和硬币问题，今天先写第一个嵌套矩形问题。

一、嵌套矩形

第一个DAG模型：矩形嵌套问题

描述

有n个矩形，每个矩形可以用a,b来描述，表示长和宽。

矩形X(a,b)可以嵌套在矩形Y(c,d)中当且仅当a

例如(1,5)可以嵌套在(6,2)内，但不能嵌套在(3,4)中。

你的任务是选出尽可能多的矩形排成一行，使得除最后一个外，每一个矩形都可以嵌套在下一个矩形内。

【分析】

矩形间的“可嵌套”关系是一个典型的二元关系，二元关系可以用图来建模。如果矩形X可以嵌套在Y中，则就从X到Y连一条有向边。这个图是无环的，因为一个矩形无法直接或或间接的嵌套在自己的内部。也即是说这是以一个DAG。

因此，我们就是在求DAG上的最长路径。

【问题】

这个是一个没有确定的路径起点和终点(可以把任意的矩形放在任何位置)的DAG问题。

如何求解，仿照上次的数字三角形(数塔)问题的求解，可以设d(i)表示从节点i出发的最长路的长度，如何写出状态转移方程呢？第一步只能走到他的相邻的节点，因此：

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

其中，E为边集。最终答案是所有的d(i)中的最大值。因此可以用递推或者记忆化搜索计算。

二、解决步骤

第一步，建图。

假如用邻接矩阵将矩形间的关系保存在矩阵G中。

第二步，编写记忆化搜索程序(调用前先初始化数组为0)。

第三步，按字典序输出最佳的方案

三、实例实践

假如有这样的五个矩形：

输入的边长分别是：

矩形宽

矩形长

3

5

4

6

2

3

7

4

6

6

其DAG表示如下：

由图可知，最长路有3--1--2 和 3--1--4

按字典序之后只有 3--1--2

具体的代码如下：(c语言实现DAG矩形嵌套问题)

附录：代码

/***** DP初步之DAG ********/

/******** written by C_Shit_Hu ************/

动态规划入门///

/****************************************************************************/

/*

第一个DAG模型：矩形嵌套问题

描述

有n个矩形，每个矩形可以用a,b来描述，表示长和宽。

矩形X(a,b)可以嵌套在矩形Y(c,d)中当且仅当a

例如(1,5)可以嵌套在(6,2)内，但不能嵌套在(3,4)中。

你的任务是选出尽可能多的矩形排成一行，使得除最后一个外，每一个矩形都可以嵌套在下一个矩形内。

输入

测试数据的第一行是一个正正数n，表示该组测试数据中含有矩形的个数(n

int j;

printf("%d ", i); // 第一次i代表最长路的起点节点，以后均代表从该节点开始的路径

for(j = 1; j

int i, j, t, ans, best;

scanf("%d", &n); // n表示矩形的数目

// 初始化矩形长宽参数，并初次调整长宽顺序

for(i = 1; i

t = x[i]; x[i] = y[i]; y[i] = t; // 保证X[]存的是长，Y[]存的是宽

}

}

memset(G, 0, sizeof(G)); // 数组清零

for(i = 1; i