有向无环图(DAG)模型是动态规划中最重要的模型之一。在众多千奇百怪的动态规划问题背后，其本质都是DAG模型，这些问题就可以转化为DAG上的经典问题求解。因此掌握好有向无环图经典问题的动态规划思路，是深入学习动态规划必不可少的一步。

一、有向无环图的经典问题求解

如下图是一张有向无环图，每条边上的边权值表示两个节点之前的距离，现在要求从节点A到节点F的最短距离：

从节点A出发，到达节点F共有以下路径：

A > B > D > F , 距离为1+5+4=10

A > B > E > F , 距离为1+8+2=11

A > C > E > F , 距离为4+3+2=9

因此，最短距离为9

我们可以用动态规划思想解决此问题，定义状态dp[i]表示从起点出发以节点 i 结尾的最短距离，对于状态dp[i]，其上一阶段可能位于它的任意前驱 j（即所有能够到达i的节点）上，那么对于节点i来说，其能做出的决策只有：从节点 j 到达节点 i，d[j]则表示从起点到达节点j的最短距离，dis[j][i]表示从节点 j 到达节点 i 的距离，那么从起点经过节点 j 到达节点 i 的最短距离就等于d[j]+dis[j][i]，由于我们要求从起点到达节点 i 的最短距离，其可能经过所有的节点 j，所以最短路径就是经过这 j 个节点的路径中最短的那条，状态转移方程如下：

dp[i] = min{dp[j] + dis[j][i] | j是i的前驱节点}

当然，我们也可以换一种状态的表示方法，我们定义dp[i]表示从节点i出发到达终点的最短距离，此时状态转移方程就变为：

dp[i] = min {dp[j] + dis[i][j] | j是i的后继节点}

最终，dp[F]就是我们要求得的从节点A到节点F的最小距离。

如果问题要求A到F的最大距离，则只要将状态及状态转移方程中的最小值换成取最大值。

另外地，我们知道动态规划问题除了最优化问题外还有一种方案数问题，即问题变为求A到F的所有路径有多少？此时也只需要将状态改为方案数，将状态转移方程改为累加求和即可。

例题1：城市交通路网

本题我们采用dp[i]表示从节点i出发的最短距离的状态来编写代码，编码思路有很多，比如采用传统的递推形式，在该状态表示下，我们需要逆序递推，才能保证i的后继是已经被计算过的。本文给出一种递归+记忆化搜索的编码形式：

#include <iostream>
#include <cstring>
using namespace std;

const int MAX_N = 100;
int n;
int dis[MAX_N + 1][MAX_N + 1];
int dp[MAX_N + 1];
int next_node[MAX_N + 1];

int solve(int i) {
    // 记忆化搜索
    if (dp[i] != 0x3f3f3f3f) {
        return dp[i];
    }
    for (int j = 1; j <= n; j++) {
        if (dis[i][j] > 0) {
            int candidate = solve(j) + dis[i][j];
            if (dp[i] > candidate) {
                dp[i] = candidate;
                next_node[i] = j;
            }
        }
    }
    return dp[i];
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> dis[i][j];
        }
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[n] = 0;
    memset(next_node, 0, sizeof(next_node));
    cout << "minlong=" << solve(1) << endl;
    cout << 1;
    int current = next_node[1];
    while (current != 0) {
        cout << " " << current;
        current = next_node[current];
    }
    cout << endl;
    return 0;
}

例题2：挖地雷

本题样例输入可以描述为如下的有向无环图：

可以看到该问题与我们上述举例的有向无环图问题存在一定差异：

1. 我们举例的DAG是边带权，而该图是节点带权；

2. 我们举例的DAG问题是确定了起点或者终点的，而本题并不确定！

怎么办呢，我们可以对该图进行一点小小的变形，添加一个虚拟节点0，其能够连接所有实际的节点，然后将节点的权值转移到边上，就可以得到下面的DAG：

此时，我们再定义状态dp[i]表示，从起点0出发，到达节点i的最长距离，是不是就跟举例的DAG问题一样了?！当然，由于终点仍然没有固定，所以最终的答案要在所有的dp[i]中取最大值。

二、有向无环图模型的拓展

例题3：最长上升子序列

大意：给定一个整数序列array，找到它的所有严格递增子序列中最长的序列，输出其长度。

例：6,3,1,5,2,3,7

它的最长上升子序列有：1, 2, 3, 7，长度为4，因此结果为4。

下面我们思考如何将其与DAG模型联系起来：

我们将每个数字都视为一个节点，对于第 i 个数字，根据题目要求，如果它后面的数字 j 满足 j>i，就满足上升子序列，那么数字 j 节点就可以作为数字 i 节点的后继，按此规则找出每个数字的后继节点，然后我们就可以据此画出如下的DAG：

题目要求最长的上升子序列，只要将该图中的边权全部视为1，是不是就变成了在该DAG中找到一条最长的路径？而这与例题2是完全相同的。于是一道全新的题型就这样被我们转化为了DAG的经典问题求解。

例题4：U157385 矩形嵌套 - 洛谷

有了例题三的经验，相信读者对于该问题应该已经能很轻松的将其转化为DAG模型了吧。

将每个矩形都看作一个节点，对于矩形 i，如果有另外一个矩形 j 满足，i的宽小于 j 的宽且 i 的长小于 j 的长或者 i 的长小于 j 的宽且 i 的宽小于 j 的长，就满足嵌套的定义，那么就可以将矩形 j 作为矩形 i 的后继节点，据此也能画出一张DAG，然后将边权视为1，问题就等价于在该DAG中找出一条最长路径。轻松搞定！

例题5：跳台阶_牛客网

楼梯共有n(100 > n > 0)阶台阶，上楼时可以一步上1阶，也可以一步上2阶，试求出走到楼梯顶一共有多少种走法？

我们在动态规划入门(一)：从爬楼梯开始中对爬楼梯问题做过讲解，现在我们以一种新的视角来重新理解一下爬楼梯问题：

将每个台阶看作一个节点，在第i级台阶，可以走到第 i+1 级台阶或第 i+2 级台阶，也就是第 i+1 级台阶与第 i+2 级台阶可以作为第i级台阶的后继节点，可以构造出如下图所示的DAG：

本题则转换为一个DAG上求路径总数的问题，求方案总数可以不关心边权，根据上文讲解的求解方法，对于任意节点 i，定义状态dp[i]表示从起点到达节点 i 的路径总数，则dp[i]就等于其所有前驱 j 的方案总数dp[j]之和，在本题中，i 的前驱就是i - 1与 i - 2，因此状态转移方程就为dp[i] = dp[i-1] + dp[i-2]。