一、DAG的定义

DAG为一个有向无环图，任意一条边有方向，但是不存在环路。

A→B→C即为有向无环图。

二、搜索与记忆化搜索

经典例题：有N个矩形，每个矩形可以用ab来描述，a和b分别为矩形的长与宽。矩形X可以嵌套在矩形Y中当且仅当a<a1&&b<b1或者a<b1&&b<a1（相当于旋转90°）时成立，一个只能嵌套一个，你的任务是选出最多可以嵌套的矩形。

1.题解：（暴力搜索思想DFS）

首先需要一个结构体：

struct node{
    int x,y;
};
node node1[150]//假设n最多有150个
int vis[400][400];//用来标记关系的数组

可以把没一个矩形都看作一个点，如果X包含Y，则vis[X][Y]=1，根据DFS的思想，先以随机一个点为起始点开始比较，如果vis[i][k]走完没有1，则说明i不能继续走了，就要return。根据这个思想，可以让程序直接走到最后，令步数=1，往上回溯时，步数+1，每次比较都找出对应的最大的步数。所以我们首先需要标记，标记代码：

    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d%d",&node1[i].x,&node1[i].y);
    for(int i=0;i<n;i++)
        for(int k=0;k<n;k++)
        {
            if(node1[i].x>node1[j].x&&node1[i].y>node1[j].y)
                vis[i][j]=1;
            if((node1[i].y>node1[j].x&&node1[i].x>node1[j].y))
                vis[i][j]=1;
        }

然后需要进行DFS：

int DFS(int u，int n)//n为矩形数量
{
    ll maxx=1;
    for(int i=0;i<n;i++)
        if(vis[u][i])//如果u矩形可以包含i矩形
            maxx=max(maxx,DFS(i，n)+1);//对矩形i继续搜索，看他是否包含了其他矩形。
    return maxx;
}
//这个程序走到无路可走时，就回回溯，毎回溯一次maxx+1,所以每一个节点都会有一个maxx,最后的结果就是maxx

上述程序是以任一点作为起始点，为保证答案的绝对正确性，需要将所有的起始点，都遍历一遍看一看。

所以在主函数中：

        ll maxx=1;
        for(int i=0;i<n;i++)
            maxx=max(maxx,DFS(i,n));
        printf("%lld",maxx);
}

maxx即为最后最大值

2.记忆化搜索

就此题而言，当4 1 1 2 2 3 3 3 3时，应该是3，当以1为出发点时，每一个节点都会走，并且每一个节点都会有他自己的maxx(维护的权值),所以，我们可以用一个数组记录一下，每一个点的权值即maxx，当权值为0时，说明这个点之后的已经都走过了，无需再走，直接return当前的权值，然后进行下一步。此方法叫做记忆化搜索：

ll ans=0;
ll dp[150];
ll DFS(int u,int n)
{
    ans++;//次数检测，用来比较搜索与记忆化搜索的复杂度，无需注意。
    if(dp[u])//如果不等于0，说明有权值，说明之后的节点都走过，且最大值都计算出开了。
        return dp[u];//直接return这个节点的权值
    ll maxx=1;
    for(int i=0;i<n;i++)
        if(vis[u][i])//如果u矩形可以包含i矩形
            maxx=max(maxx,DFS(i,n)+1);
    return dp[u]=maxx;//没走过return重新得到的权值
}

而且我们也可以很清楚用ans记录步数，发现原本是11，现在只需要9，当数据大时肯定会减少很多。

三、动态规划

关于以上问题我们可以首先对矩形进行排序：

bool cmp(node a,node b)
{
    if(a.x==b.x)
        return a.y<b.x;
    return a.x<b.x;
}

排序后，我们可以想，矩形i可以嵌套的矩形数量等于他嵌套的矩形可以嵌套矩形的数量+1，最多的话应在这些选择之中加个max选出最大值。

int dp[150];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d%d",&node1[i].x,&node1[i].y);
    sort(node1,node1+n,cmp);
    for(int i=0;i<n;i++)
    {
        dp[i]=1;//第一个矩形肯定能嵌套一个就是他自己。
        for(int k=0;k<i;k++)
        {

            if(node1[i].x>node1[k].x&&node1[i].y>node1[k].y)
                dp[i]=max(dp[i],dp[k]+1);//他能嵌套的矩形数量，=，他嵌套的矩形能嵌套矩形的数量+1。
            if(node1[i].y>node1[k].x&&node1[i].x>node1[k].y)
                dp[i]=max(dp[i],dp[k]+1);
        }
    }
    //通过这两个for循环，就把从0-n序号的矩形，所能包含的最大矩形数量找出来了。
    //用max函数求出最大值就好。
    int maxx=1;
    for(int i=0;i<n;i++)
        maxx=max(maxx,dp[i]);
    printf("%d",maxx);
}

方程 dp[i]=max(dp[i],dp[k]+1)称为状态转移方程

四、总结

1.此类记忆化搜索与动态规划只是用与DGA，也就是用图来表示的话，应该是一个有向无环图。

2.记忆化搜索与动态规划类似，都是将每一个节点的最大值保存起来，作为他的权值，最后输出。

3.加油，继续加油！