DAG上的DP实例讲解
DAG是学习动态规划的基础，（DAG：有向无环图。）很多问题都可以直接转化为DAG上的最长路、最短路或路径计数问题。
两个经典的DAG模型，嵌套矩形和硬币问题。
一、嵌套矩形
（1）第一个DAG模型：矩形嵌套问题
描述：有n个矩形，每个矩形可以用a,b来描述，表示长和宽。
矩形X(a,b)可以嵌套在矩形Y(c,d)中当且仅当a<c,b<d或者b<c,a<d（相当于旋转X90度）。
例如（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）中的最大值。因此可以用递推或者记忆化搜索计算。
（2）解决步骤
第一步，建图。假如用邻接矩阵将矩形间的关系保存在矩阵G中。
第二步，编写记忆化搜索程序（调用前先初始化数组为0）。
第三步，按字典序输出最佳的方案
（3）实例实践
假如有这样的五个矩形：
输入的边长分别是：
| 矩形宽 | 矩形长 |
| 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<c,b<d或者b<c,a<d（相当于旋转X90度）。
例如（1,5）可以嵌套在（6,2）内，但不能嵌套在（3,4）中。
你的任务是选出尽可能多的矩形排成一行，使得除最后一个外，每一个矩形都可以嵌套在下一个矩形内。
输入
测试数据的第一行是一个正正数n，表示该组测试数据中含有矩形的个数(n<=1000)
随后的n行，每行有两个数a,b(0<a,b<100)，表示矩形的长和宽
输出
每组测试数据都输出一个数，表示最多符合条件的矩形数目，每组输出占一行
*/
/****************************************************************************/
// 思路：先对长和宽来此排序，再按照要求构图，
// 完成之后，直接记忆化搜索，值得注意的地方是你不能只从第一个点搜索，而是要从每个点搜索
#include<stdio.h>
#include<string.h>
#define MAXN 101
int n, G[MAXN][MAXN]; // 图的存储
int x[MAXN], y[MAXN], d[MAXN]; // 节点
//记忆化搜索来完成的动态转移
int dp(int i)
{
int j;
if(d[i] > 0)
return d[i]; // 如果已经计算过，直接返回其值
d[i] = 1; // 否则，置一，递推计算
for(j = 1; j <= n; j++)
if(G[i][j]) // 如果图存在，即是满足可嵌套
if(d[i] <=dp(j)+1) // 如果存在可嵌套的节点d(j)加一后其值大于d(i)
d[i]=dp(j)+1; // 则使d[i]更新
return d[i]; // 返回d[i]
}
//按字典序只输出排序最小的序列
/*
此部分的原理：字典序只是消除并列名次的方法，我们最根本的任务还是求出最长路
在把所有的d值计算出来后，选择最大的d[i]所对应的i。而如果有多个i，则选择最小的i，这样保证字典序最小。
接下来选择d(i) = d(j) +1 且i, j ∈E 的任何一个j，但是为满足字典序最小，需选择最小的j
*/
void print_ans(int i)
{
int j;
printf("%d ", i); // 第一次i代表最长路的起点节点，以后均代表从该节点开始的路径
for(j = 1; j <= n; j++)
if(G[i][j] && d[i] == d[j]+1) // 如果该图满足可嵌套，且d[i] = d[j] +1
{
print_ans(j); // 立即输出从节点j开始的路径
break;
}
}
int main()
{
int i, j, t, ans, best;
scanf("%d", &n); // n表示矩形的数目
// 初始化矩形长宽参数，并初次调整长宽顺序
for(i = 1; i <= n; i++)
{
scanf("%d%d", &x[i], &y[i]); // 依次输入矩形的边长信息
if(x[i] > y[i])
{
t = x[i]; x[i] = y[i]; y[i] = t; // 保证X[]存的是长，Y[]存的是宽
}
}
memset(G, 0, sizeof(G)); // 数组清零
for(i = 1; i <= n; i++) // 建图
for(j = 1; j <= n; j++)
if(x[i] < x[j] && y[i] < y[j]) G[i][j] = 1; // 如果第i个矩形的长宽均小于第j个，使图相应的值为1
ans = 0;
for(i = 1; i <= n; i++) // 依次递推所有的的节点
if(dp(i) > ans)
{
best = i; // best 是最小字典序
ans = dp(i);
}
printf("ans=%d\n", ans); // 表示最长路长度
print_ans(best);
printf("\n");
while(1);
return 0 ;
}
/******************************************************/
/******************** 心得体会 **********************/
/*
好好学习DP！！！
*/
/******************************************************/二、硬币问题DP
【问题描述】
有n种硬币，面值分别为V1，V2，V3，.....Vn，每种都有无限多。
给定非负整数S，可以选用多少个硬币，使得面值之和恰好为S？
输出硬币数目的最小值和最大值。1<=n>=100, 0<=S<=10000,1<=Vi<=S.
【分析与思路】
思路：本题是固定终点和起点的DAG动态规划。
我们把每种面值看做一个点，表示“还需要凑足的面值”，则初始状态为S，目标状态为0。
如当前在状态i，没使用一个硬币j，状态变转移到i-Vj。
有n种硬币，面值分别为V1，V2，V3，.....Vn，每种都有无限多。
给定非负整数S，可以选用多少个硬币，使得面值之和恰好为S？
输出硬币数目的最小值和最大值。1<=n>=100, 0<=S<=10000,1<=Vi<=S.
本题是固定终点和起点的DAG动态规划。
我们把每种面值看做一个点，表示“还需要凑足的面值”，则初始状态为S，目标状态为0。
如当前在状态i，没使用一个硬币j，状态变转移到i-Vj。
递推方法实现
#include<stdio.h>
#include<string.h>
#define MAX 10001
#define INF 1000000000;
int n, S;
int V[MAX] ,vis[MAX], d[MAX];
int max[MAX], min[MAX] ;
// 输出最小字典序
void prit_ans(int *d, int S)
{
int i;
for( i=1; i<=n; i++)
if (S>=V[i] && d[S] == d[S-V[i]] +1)
{
printf("%d ", i);
prit_ans(d, S-V[i]) ;
break ;
}
}
// 主函数、递推实现最短路最长路
int main ()
{
memset(min,0,sizeof(min));
memset(max,0,sizeof(max));
memset(V,0,sizeof(V));
int i ,j ;
min[0] = max[0] = 0;
printf("请输入要组成的面值之和S：");
scanf("%d", &S) ;
printf("请输入不同面值的硬币的种类：");
scanf("%d", &n) ;
printf("请输入各个种类的硬币的面值：\n");
for (i=1; i<=n; i++)
{
scanf("%d", &V[i]);
}
// 递推算法求解最长最短路
for (i=1; i<=S; i++)///初始化min初始化为最大值，max初始化为最小值
{
min[i] = INF;
max[i] = -INF;
}
for (i=1; i <= S; i++)///表示的钱数
for (j=1; j<=n; j++)///对应的个数
if(i >= V[j])///当需要表示的钱币数大于硬币所能表示的数值时，才可以往下进行
{
///对min和max进行更新
if (min[i] >= (min[i-V[j]] +1))
min[i] = min[i-V[j]] +1;
if (max[i] <= (max[i-V[j]] +1))
max[i] = max[i-V[j]] +1;
}
printf("%d %d\n", min[S], max[S]);
// 输出最优字典序
prit_ans(min, S);
printf("\n");
prit_ans(max, S) ;
printf("\n");
return 0 ;
}记忆化搜索方法实现。里面加标记的地方为输出字典序最小的序列
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
using namespace std;
struct data
{
int x;
int y;
} a[1010];
int G[1010][1010];
int dp[1010];
int n;
int d(int i)
{
int& ans = dp[i];
if(ans > 0)
return ans;
ans = 1;
for(int j = 0; j < n; j ++)
if(G[i][j])
ans = max(ans,d(j) + 1);
return ans;
}
/*
void print_ans(int i)
{
printf("%d ",i);
for(int j = 1; j <= n; j ++)
if(G[i][j] && dp[i] == dp[j]+1)
{
print_ans(j);
break;
}
}
*/
int main()
{
int t;
scanf("%d",&t);
while(t --)
{
memset(dp,0,sizeof(dp));
memset(G,0,sizeof(G));
scanf("%d",&n);
for(int i = 0; i < n; i ++)
scanf("%d%d",&a[i].x,&a[i].y);
for(int i = 0; i < n; i ++)
for(int j = 0; j < n; j ++)
if(a[j].x < a[i].x && a[j].y < a[i].y || (a[j].y < a[i].x && a[j].x < a[i].y))
G[i][j] = 1;
int maxx = -1,k;
for(int i = 0; i < n; i ++)
{
int t = d(i);
if(maxx < t)
{
k = i;
maxx = t;
}
}
cout << maxx << endl;
//print_ans(k);
}
return 0;
}知识点标签：动态规划
本文固定URL：https://www.dotcpp.com/course/985
区间DP实例讲解
下一课：树形DP概念和实例讲解
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程