DAG是學(xué)習(xí)動(dòng)態(tài)規(guī)劃的基礎(chǔ)，（DAG：有向無環(huán)圖。）很多問題都可以直接轉(zhuǎn)化為DAG上的最長(zhǎng)路、最短路或路徑計(jì)數(shù)問題。
兩個(gè)經(jīng)典的DAG模型，嵌套矩形和硬幣問題。
一、嵌套矩形
（1）第一個(gè)DAG模型：矩形嵌套問題
描述：有n個(gè)矩形，每個(gè)矩形可以用a,b來描述，表示長(zhǎng)和寬。
矩形X(a,b)可以嵌套在矩形Y(c,d)中當(dāng)且僅當(dāng)a<c,b<d或者b<c,a<d（相當(dāng)于旋轉(zhuǎn)X90度）。
例如（1,5）可以嵌套在（6,2）內(nèi)，但不能嵌套在（3,4）中。
你的任務(wù)是選出盡可能多的矩形排成一行，使得除最后一個(gè)外，每一個(gè)矩形都可以嵌套在下一個(gè)矩形內(nèi)。
【分析】
矩形間的“可嵌套”關(guān)系是一個(gè)典型的二元關(guān)系，二元關(guān)系可以用圖來建模。如果矩形X可以嵌套在Y中，則就從X到Y(jié)連一條有向邊。這個(gè)圖是無環(huán)的，因?yàn)橐粋€(gè)矩形無法直接或或間接的嵌套在自己的內(nèi)部。也即是說這是以一個(gè)DAG。
因此，我們就是在求DAG上的最長(zhǎng)路徑。
【問題】
這個(gè)是一個(gè)沒有確定的路徑起點(diǎn)和終點(diǎn)（可以把任意的矩形放在任何位置）的DAG問題。
如何求解，仿照上次的數(shù)字三角形（數(shù)塔）問題的求解，可以設(shè)d（i）表示從節(jié)點(diǎn)i出發(fā)的最長(zhǎng)路的長(zhǎng)度，如何寫出狀態(tài)轉(zhuǎn)移方程呢？第一步只能走到他的相鄰的節(jié)點(diǎn)，因此：
d（i）= max { d（j）+1 | i, j ∈E }
其中，E為邊集。最終答案是所有的d（i）中的最大值。因此可以用遞推或者記憶化搜索計(jì)算。
（2）解決步驟
第一步，建圖。假如用鄰接矩陣將矩形間的關(guān)系保存在矩陣G中。
第二步，編寫記憶化搜索程序（調(diào)用前先初始化數(shù)組為0）。
第三步，按字典序輸出最佳的方案
（3）實(shí)例實(shí)踐
假如有這樣的五個(gè)矩形：
輸入的邊長(zhǎng)分別是：
| 矩形寬 | 矩形長(zhǎng) |
| 3 | 5 |
| 4 | 6 |
| 2 | 3 |
| 7 | 4 |
| 6 | 6 |
其DAG表示如下：
由圖可知，最長(zhǎng)路有3--1--2 和 3--1--4
按字典序之后只有 3--1--2
具體的代碼如下：（c語言實(shí)現(xiàn)DAG矩形嵌套問題）
/***** DP初步之DAG ********/
/******** written by C_Shit_Hu ************/
動(dòng)態(tài)規(guī)劃入門///
/****************************************************************************/
/*
第一個(gè)DAG模型：矩形嵌套問題
描述
有n個(gè)矩形，每個(gè)矩形可以用a,b來描述，表示長(zhǎng)和寬。
矩形X(a,b)可以嵌套在矩形Y(c,d)中當(dāng)且僅當(dāng)a<c,b<d或者b<c,a<d（相當(dāng)于旋轉(zhuǎn)X90度）。
例如（1,5）可以嵌套在（6,2）內(nèi)，但不能嵌套在（3,4）中。
你的任務(wù)是選出盡可能多的矩形排成一行，使得除最后一個(gè)外，每一個(gè)矩形都可以嵌套在下一個(gè)矩形內(nèi)。
輸入
測(cè)試數(shù)據(jù)的第一行是一個(gè)正正數(shù)n，表示該組測(cè)試數(shù)據(jù)中含有矩形的個(gè)數(shù)(n<=1000)
隨后的n行，每行有兩個(gè)數(shù)a,b(0<a,b<100)，表示矩形的長(zhǎng)和寬
輸出
每組測(cè)試數(shù)據(jù)都輸出一個(gè)數(shù)，表示最多符合條件的矩形數(shù)目，每組輸出占一行
*/
/****************************************************************************/
// 思路：先對(duì)長(zhǎng)和寬來此排序，再按照要求構(gòu)圖，
// 完成之后，直接記憶化搜索，值得注意的地方是你不能只從第一個(gè)點(diǎn)搜索，而是要從每個(gè)點(diǎn)搜索
#include<stdio.h>
#include<string.h>
#define MAXN 101
int n, G[MAXN][MAXN]; // 圖的存儲(chǔ)
int x[MAXN], y[MAXN], d[MAXN]; // 節(jié)點(diǎn)
//記憶化搜索來完成的動(dòng)態(tài)轉(zhuǎn)移
int dp(int i)
{
int j;
if(d[i] > 0)
return d[i]; // 如果已經(jīng)計(jì)算過，直接返回其值
d[i] = 1; // 否則，置一，遞推計(jì)算
for(j = 1; j <= n; j++)
if(G[i][j]) // 如果圖存在，即是滿足可嵌套
if(d[i] <=dp(j)+1) // 如果存在可嵌套的節(jié)點(diǎn)d(j)加一后其值大于d(i)
d[i]=dp(j)+1; // 則使d[i]更新
return d[i]; // 返回d[i]
}
//按字典序只輸出排序最小的序列
/*
此部分的原理：字典序只是消除并列名次的方法，我們最根本的任務(wù)還是求出最長(zhǎng)路
在把所有的d值計(jì)算出來后，選擇最大的d[i]所對(duì)應(yīng)的i。而如果有多個(gè)i，則選擇最小的i，這樣保證字典序最小。
接下來選擇d(i) = d(j) +1 且i, j ∈E 的任何一個(gè)j，但是為滿足字典序最小，需選擇最小的j
*/
void print_ans(int i)
{
int j;
printf("%d ", i); // 第一次i代表最長(zhǎng)路的起點(diǎn)節(jié)點(diǎn)，以后均代表從該節(jié)點(diǎn)開始的路徑
for(j = 1; j <= n; j++)
if(G[i][j] && d[i] == d[j]+1) // 如果該圖滿足可嵌套，且d[i] = d[j] +1
{
print_ans(j); // 立即輸出從節(jié)點(diǎn)j開始的路徑
break;
}
}
int main()
{
int i, j, t, ans, best;
scanf("%d", &n); // n表示矩形的數(shù)目
// 初始化矩形長(zhǎng)寬參數(shù)，并初次調(diào)整長(zhǎng)寬順序
for(i = 1; i <= n; i++)
{
scanf("%d%d", &x[i], &y[i]); // 依次輸入矩形的邊長(zhǎng)信息
if(x[i] > y[i])
{
t = x[i]; x[i] = y[i]; y[i] = t; // 保證X[]存的是長(zhǎng)，Y[]存的是寬
}
}
memset(G, 0, sizeof(G)); // 數(shù)組清零
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個(gè)矩形的長(zhǎng)寬均小于第j個(gè)，使圖相應(yīng)的值為1
ans = 0;
for(i = 1; i <= n; i++) // 依次遞推所有的的節(jié)點(diǎn)
if(dp(i) > ans)
{
best = i; // best 是最小字典序
ans = dp(i);
}
printf("ans=%d\n", ans); // 表示最長(zhǎng)路長(zhǎng)度
print_ans(best);
printf("\n");
while(1);
return 0 ;
}
/******************************************************/
/******************** 心得體會(huì) **********************/
/*
好好學(xué)習(xí)DP?。?！
*/
/******************************************************/二、硬幣問題DP
【問題描述】
有n種硬幣，面值分別為V1，V2，V3，.....Vn，每種都有無限多。
給定非負(fù)整數(shù)S，可以選用多少個(gè)硬幣，使得面值之和恰好為S？
輸出硬幣數(shù)目的最小值和最大值。1<=n>=100, 0<=S<=10000,1<=Vi<=S.
【分析與思路】
思路：本題是固定終點(diǎn)和起點(diǎn)的DAG動(dòng)態(tài)規(guī)劃。
我們把每種面值看做一個(gè)點(diǎn)，表示“還需要湊足的面值”，則初始狀態(tài)為S，目標(biāo)狀態(tài)為0。
如當(dāng)前在狀態(tài)i，沒使用一個(gè)硬幣j，狀態(tài)變轉(zhuǎn)移到i-Vj。
有n種硬幣，面值分別為V1，V2，V3，.....Vn，每種都有無限多。
給定非負(fù)整數(shù)S，可以選用多少個(gè)硬幣，使得面值之和恰好為S？
輸出硬幣數(shù)目的最小值和最大值。1<=n>=100, 0<=S<=10000,1<=Vi<=S.
本題是固定終點(diǎn)和起點(diǎn)的DAG動(dòng)態(tài)規(guī)劃。
我們把每種面值看做一個(gè)點(diǎn)，表示“還需要湊足的面值”，則初始狀態(tài)為S，目標(biāo)狀態(tài)為0。
如當(dāng)前在狀態(tài)i，沒使用一個(gè)硬幣j，狀態(tài)變轉(zhuǎn)移到i-Vj。
遞推方法實(shí)現(xiàn)
#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 ;
}
}
// 主函數(shù)、遞推實(shí)現(xiàn)最短路最長(zhǎng)路
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("請(qǐng)輸入要組成的面值之和S：");
scanf("%d", &S) ;
printf("請(qǐng)輸入不同面值的硬幣的種類：");
scanf("%d", &n) ;
printf("請(qǐng)輸入各個(gè)種類的硬幣的面值：\n");
for (i=1; i<=n; i++)
{
scanf("%d", &V[i]);
}
// 遞推算法求解最長(zhǎng)最短路
for (i=1; i<=S; i++)///初始化min初始化為最大值，max初始化為最小值
{
min[i] = INF;
max[i] = -INF;
}
for (i=1; i <= S; i++)///表示的錢數(shù)
for (j=1; j<=n; j++)///對(duì)應(yīng)的個(gè)數(shù)
if(i >= V[j])///當(dāng)需要表示的錢幣數(shù)大于硬幣所能表示的數(shù)值時(shí)，才可以往下進(jìn)行
{
///對(duì)min和max進(jìn)行更新
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]);
// 輸出最優(yōu)字典序
prit_ans(min, S);
printf("\n");
prit_ans(max, S) ;
printf("\n");
return 0 ;
}記憶化搜索方法實(shí)現(xiàn)。里面加標(biāo)記的地方為輸出字典序最小的序列
#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;
}C語言網(wǎng)提供由在職研發(fā)工程師或ACM藍(lán)橋杯競(jìng)賽優(yōu)秀選手錄制的視頻教程，并配有習(xí)題和答疑，點(diǎn)擊了解：
一點(diǎn)編程也不會(huì)寫的：零基礎(chǔ)C語言學(xué)練課程
解決困擾你多年的C語言疑難雜癥特性的C語言進(jìn)階課程
從零到寫出一個(gè)爬蟲的Python編程課程
只會(huì)語法寫不出代碼？手把手帶你寫100個(gè)編程真題的編程百練課程
信息學(xué)奧賽或C++選手的 必學(xué)C++課程
藍(lán)橋杯ACM、信息學(xué)奧賽的必學(xué)課程：算法競(jìng)賽課入門課程
手把手講解近五年真題的藍(lán)橋杯輔導(dǎo)課程