DAG上的DP (拓扑序DP)，无权 DAG 的最长路径

字数统计: 2.8k字 | 阅读时长: 12分

2020-10-13

摘要: 拓扑序DP解无权DAG上的最长路径问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

对于一个 DAG，我们可以进行拓扑排序，一些动态规划的问题，其阶段的推导过程呈现为一个 DAG，形成了图上的动态规划。

对于图上的动态规划，一般以节点在图上距离起点的最长步数作为 DP 的阶段。阶段之间以拓扑序进行推导。

如下图，起点视为 1 阶段，节点 5 到起点的最长步数为 2，所以即使从起点一步就可以到节点 5，节点 5 仍然是 3 阶段的点，在求该点之前需要将所有 2 阶段以及更低阶段的节点先算完，这正是拓扑排序的要求。

DAG 上的 DP

状态表示的第一维是节点编号，隐含了阶段信息。转移方程的形式大致如下，其中 $uv$ 是 DAG 中的有向边：

$dp[u] = f(dp[v_{1}], dp[v_{2}],\cdots)$

推导状态的时候，按照 BFS 拓扑序进行推导，还是按照 DFS 拓扑序进行推导，需要根据需求来分析。

如果按照 BFS 拓扑序推导，状态定义一般为 $dp[v]$ 表示以 $v$ 为终点的某种指标，当计算 $dp[v]$ 时，所有父节点 $u$ 的 $dp[u]$ 已经计算完。

如果按照 DFS 拓扑序推导，状态定义一般为 $dp[u]$ 表示已 $u$ 为起点的某种指标。当计算 $dp[u]$ 时，所有子节点 $v$ 的 $dp[v]$ 已经计算完。

本文我们首先介绍拓扑序 DP 的思想，然后解决无权 DAG 的最长路径问题，一共涉及三道题。

$1 拓扑序(DFS 序 / BFS 序)

作为对比，有很多图上的动态规划问题实际上并不以图的节点作为阶段，阶段另有其它维度并有其物理意义，此时节点是作为阶段持有的状态存在的，转移方程具有以下这样的形式

1	dp[u][i] = f(u, i, dp[v][i - 1])

阶段的维度是 i，并且线性推导，而阶段持有一个状态维度 u，u 决定了下一个阶段可以持有哪些状态。

而对于 DAG 上的动态规划问题，有时节点本身就是阶段，并且具有物理意义

当 u 本身是阶段的时候，状态的推导顺序就很重要了，而拓扑排序是此时决定状态推导顺序的最常用的一种方法。此时状态的转移就很直观，类似与以下形式

1	dp[u] = f(dp[v])

其中 u 本身就是阶段 v 是拓扑排序中 u 的下一个点。而不是有另外的维度 i 表示阶段并持有 u 这样一个状态。

按照 BFS 拓扑序推导还是按照 DFS 拓扑序推导需要根据需求来分析。

有时可以转换一下状态的定义，原来 BFS 拓扑序 DP 的状态定义为 dp[v] := 以 v 为终点..., 可以变为 dp[u] := 以 u 为起点...，之后可以直接用 DFS 序 DP(记忆化搜索)。

$2 无权 DAG 最长路径

329. 矩阵中的最长递增路径

给定一个 m x n 整数矩阵 matrix ，找出其中最长递增路径的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 2^31 - 1

示例 1：
输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出：4
解释：最长递增路径为 [1, 2, 6, 9]。

示例 2：
输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出：4
解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
示例 3：
输入：matrix = [[1]]
输出：1

分析

无权 DAG 未指定源点的最长路径。

代码 (BFS 拓扑序 DP)

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if(matrix.empty()) return 0;
        int n = matrix.size(), m = matrix[0].size();
        int dx[4] = {0, 1, 0, -1};
        int dy[4] = {1, 0, -1, 0};
        vector<vector<int> > outdegrees(n, vector<int>(m, 0));
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
                for(int d = 0; d < 4; ++d)
                {
                    int x = i + dx[d];
                    int y = j + dy[d];
                    if(x >= 0 && x < n && y >= 0 && y < m && matrix[i][j] < matrix[x][y])
                        ++outdegrees[i][j];
                }
        using PII = pair<int, int>;
        queue<PII> q;
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
                if(outdegrees[i][j] == 0)
                    q.push(PII(i, j));

        int result = 0;
        vector<PII> level_nodes;
        while(!q.empty())
        {
            ++result;
            level_nodes.clear();
            while(!q.empty())
            {
                level_nodes.push_back(q.front());
                q.pop();
            }
            for(PII p: level_nodes)
            {
                int i = p.first;
                int j = p.second;
                for(int d = 0; d < 4; ++d)
                {
                    int x = i + dx[d];
                    int y = j + dy[d];
                    if(x >= 0 && x < n && y >= 0 && y < m && matrix[i][j] > matrix[x][y])
                        if(--outdegrees[x][y] == 0)
                            q.push(PII(x, y));
                }
            }
        }
        return result;
    }
};

1340. 跳跃游戏 V

给你一个整数数组 arr 和一个整数 d 。每一步你可以从下标 i 跳到：

i + x ，其中 i + x < arr.length 且 0 < x <= d 。
i - x ，其中 i - x >= 0 且 0 < x <= d 。

除此以外，你从下标 i 跳到下标 j 需要满足：arr[i] > arr[j] 且 arr[i] > arr[k] ，其中下标 k 是所有 i 到 j 之间的数字（更正式的，min(i, j) < k < max(i, j)）。

你可以选择数组的任意下标开始跳跃。请你返回你最多可以访问多少个下标。

请注意，任何时刻你都不能跳到数组的外面。

提示：

1
2
3

1 <= arr.length <= 1000
1 <= arr[i] <= 10^5
1 <= d <= arr.length

示例 1：
输入：arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
输出：4
解释：你可以从下标 10 出发，然后如上图依次经过 10 —> 8 —> 6 —> 7 。
注意，如果你从下标 6 开始，你只能跳到下标 7 处。你不能跳到下标 5 处因为 13 > 9 。你也不能跳到下标 4 处，因为下标 5 在下标 4 和 6 之间且 13 > 9 。
类似的，你不能从下标 3 处跳到下标 2 或者下标 1 处。

示例 2：
输入：arr = [3,3,3,3,3], d = 3
输出：1
解释：你可以从任意下标处开始且你永远无法跳到任何其他坐标。

示例 3：
输入：arr = [7,6,5,4,3,2,1], d = 1
输出：7
解释：从下标 0 处开始，你可以按照数值从大到小，访问所有的下标。

示例 4：
输入：arr = [7,1,7,1,7,1], d = 2
输出：2

示例 5：
输入：arr = [66], d = 1
输出：1

分析

各个下标的关系是无权有向图。由于有高度限制，有向图必然无环。

在这个 DAG 上求最长路，但是出发点和终点都没有给定。可以加一个超级源也可以枚举所有起点。

dp[u] := 以 u 为起点的最长路径

转移
dp[u] = 1 + dp[v]  v 满足某些条件

记忆化过程：
dp[u] = -1 : u 未访问过
dp[u] = 0 : 前面访问过 u, 但尚未返回答案

记忆化的过程隐含着做了一轮 DFS (但不是拓扑排序)，即按照 DFS 序的顺序推导状态。

代码 (DFS 拓扑序 DP)

转换状态定义后记忆化搜索

class Solution {
public:
    int maxJumps(vector<int>& arr, int d) {
        if(arr.empty()) return 0;
        int n = arr.size();
        dp = vector<int>(n, -1);
        int ans = 1;
        for(int i = 0; i < n; ++i)
            if(dp[i] == -1)
                ans = max(ans, solve(arr, d, i));
        return ans;
    }

private:
    // dp[i] := 以 i 开头的最长路径
    vector<int> dp;

    int solve(const vector<int>& arr, const int d, int pos)
    {
        if(dp[pos] != -1)
            return dp[pos];
        dp[pos] = 0;
        int n = arr.size();
        for(int k = 1; k <= d; ++k)
        {
            int nxt = pos + k;
            if(nxt >= n || arr[pos] <= arr[nxt])
                break;
            dp[pos] = max(dp[pos], 1 + solve(arr, d, nxt));
        }
        for(int k = 1; k <= d; ++k)
        {
            int nxt = pos - k;
            if(nxt < 0 || arr[pos] <= arr[nxt])
                break;
            dp[pos] = max(dp[pos], 1 + solve(arr, d, nxt));
        }
        dp[pos] = max(1, dp[pos]);
        return dp[pos];
    }
};

1048. 最长字符串链

给出一个单词数组 words ，其中每个单词都由小写英文字母组成。

如果我们可以不改变其他字符的顺序，在 wordA 的任何地方添加恰好一个字母使其变成 wordB ，那么我们认为 wordA 是 wordB 的前身。

例如，”abc” 是 “abac” 的前身，而 “cba” 不是 “bcad” 的前身

词链是单词 [word_1, word_2, …, word_k] 组成的序列，k >= 1，其中 word1 是 word2 的前身，word2 是 word3 的前身，依此类推。一个单词通常是 k == 1 的单词链。

从给定单词列表 words 中选择单词组成词链，返回词链的最长可能长度。

提示：

1
2
3

1 <= words.length <= 1000
1 <= words[i].length <= 16
words[i] 仅由小写英文字母组成。

示例 1：
输入：words = [“a”,”b”,”ba”,”bca”,”bda”,”bdca”]
输出：4
解释：最长单词链之一为 [“a”,”ba”,”bda”,”bdca”]

示例 2:
输入：words = [“xbc”,”pcxbcf”,”xb”,”cxbc”,”pcxbc”]
输出：5
解释：所有的单词都可以放入单词链 [“xb”, “xbc”, “cxbc”, “pcxbc”, “pcxbcf”].

示例 3:
输入：words = [“abcd”,”dbqca”]
输出：1
解释：字链[“abcd”]是最长的字链之一。
[“abcd”，”dbqca”]不是一个有效的单词链，因为字母的顺序被改变了。

分析

各个字符串的关系是无权有向图。由于字符串长度的限制，此有向图是无环的。

在这个 DAG 上求最长路，但是出发点和终点都没有给定。可以加一个超级源也可以枚举所有起点。

代码 (DFS 拓扑序 DP)

转换状态定义后记忆化搜索

class Solution {
public:
    int longestStrChain(vector<string>& words) {
        int n = words.size();
        vector<vector<int> > g(n);
        vector<int> indegrees(n);
        for(int i = 0; i < (n - 1); ++i)
            for(int j = i + 1; j < n; ++j)
            {
                int li = words[i].size(), lj = words[j].size();
                if(li + 1 == lj && check(words[i], words[j]))
                {
                    // i 是 j 前驱
                    g[i].push_back(j);
                    ++indegrees[j];
                }
                if(lj + 1 == li && check(words[j], words[i]))
                {
                    // j 是 i 前驱
                    g[j].push_back(i);
                    ++indegrees[i];
                }
            }
        vector<int> dp(n, -1); // dp[i] := 以 i 为起点的最长链
        for(int i = 0; i < n; ++i)
            if(g[i].empty())
                dp[i] = 1;
        int ans = 0;
        for(int i = 0; i < n; ++i)
            if(indegrees[i] == 0)
            {
                ans = max(ans, solve(i, g, dp));
            }
        return ans;
    }

private:
    int solve(int i, const vector<vector<int> >& g, vector<int>& dp)
    {
        if(dp[i] != -1)
            return dp[i];

        dp[i] = 0;
        for(int son: g[i])
            dp[i] = max(dp[i], solve(son, g, dp));
        ++dp[i];
        return dp[i];
    }

    bool check(const string& s1, const string& s2)
    {
        // 调用方保证 l1 + 1 == l2
        int l1 = s1.size();
        int i1 = 0, i2 = 0;
        int cnt = 1;
        while(i1 < l1)
        {
            if(s1[i1] != s2[i2]) // 需要插入 s2[i2]
            {
                --cnt;
                if(cnt < 0) return false;
            }
            else
                ++i1;
            ++i2;
        }
        return true;
    }
};

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法动态规划

DAG上的DP (拓扑序DP)，无权 DAG 的最长路径

$1 拓扑序(DFS 序 / BFS 序)

$2 无权 DAG 最长路径

329. 矩阵中的最长递增路径

分析

代码 (BFS 拓扑序 DP)

1340. 跳跃游戏 V

分析

代码 (DFS 拓扑序 DP)

1048. 最长字符串链

分析

代码 (DFS 拓扑序 DP)