如何高效计算符合指定DFS遍历顺序的树的数量？

问题描述 #

给定一棵根为1的树（不限定为二叉树），需计算所有与原树具有完全相同DFS遍历序列的树的总数。例如，当DFS序列为{1,2,3}时，答案为2，对应两棵树：

• 链状结构：1→2→3
• 星型结构：1同时连接2和3

注：此处的DFS遍历严格按照节点编号升序访问邻接点，对应的Python代码逻辑如下：

def dfs(u):
    print(u)
    vis[u] = True
    # 按节点编号从1到n升序遍历
    for i in range(1, n + 1):
        # 若i是u的邻接点且未被访问，则递归遍历
        if i in adj(u) and not vis[i]:
            dfs(i)

高效计数方法（节点数≤100） #

我们采用**区间动态规划（DP）**结合记忆化的方式实现高效计数，时间复杂度为O(n³)，对于n=100完全可行。

核心思路 #

给定DFS序列S = [s₀, s₁, ..., sₙ₋₁]（其中s₀=1），定义dp[l][r]为：以s[l]为根，且DFS遍历序列恰好为S[l..r]（闭区间）的树的数量。

利用DFS遍历的特性：根节点的子节点必须按编号升序访问，因此每个子节点对应的DFS子序列是连续的一段，且子节点的编号严格递增。

DP状态转移 #

1. 基础情况：

   • 当l == r时，dp[l][r] = 1（单个节点无任何子节点，仅有一种结构）。
   • 当l > r时，dp[l][r] = 1（空树，作为乘法运算的单位元）。

2. 状态转移：
   对于l < r的情况，根节点是s[l]，其第一个子节点必然是s[l+1]（按升序访问规则）。我们枚举第一个子节点对应的子树结束位置m（从l+1到r）：

   • 若m == r：表示第一个子节点的子树覆盖了l+1到r的所有节点，此时总数累加dp[l+1][m] * dp[m+1][r]（dp[m+1][r]为1）。
   • 若m < r：需保证下一个子节点的编号s[m+1] > s[l+1]（符合升序访问规则），此时总数累加dp[l+1][m] * dp[m+1][r]。

实现方式 #

记忆化搜索实现

def count_valid_trees(S):
    n = len(S)
    memo = [[-1] * n for _ in range(n)]

    def dp(l, r):
        if l >= r:
            return 1
        if memo[l][r] != -1:
            return memo[l][r]
        res = 0
        first_child = S[l+1]
        m = l + 1
        while m <= r:
            if m == r or S[m+1] > first_child:
                res += dp(l+1, m) * dp(m+1, r)
            m += 1
        memo[l][r] = res
        return res

    return dp(0, n-1)

# 示例：DFS序列为[1,2,3]
S = [1,2,3]
print(count_valid_trees(S))  # 输出2

迭代DP实现

def count_valid_trees(S):
    n = len(S)
    dp = [[0] * n for _ in range(n)]

    # 初始化长度为1的区间
    for i in range(n):
        dp[i][i] = 1

    # 按区间长度从小到大计算
    for length in range(2, n+1):
        for l in range(n - length + 1):
            r = l + length - 1
            res = 0
            first_child = S[l+1]
            m = l + 1
            while m <= r:
                right_part = dp[m+1][r] if (m+1 <= r) else 1
                if m == r or S[m+1] > first_child:
                    res += dp[l+1][m] * right_part
                m += 1
            dp[l][r] = res

    return dp[0][n-1]

# 示例：DFS序列为[1,2,3]
S = [1,2,3]
print(count_valid_trees(S))  # 输出2

验证示例 #

对于DFS序列[1,2,3]：

• dp[0][2] = dp[1][2] * dp[3][2] + dp[1][1] * dp[2][2] = 1*1 + 1*1 = 2，与预期结果一致。

对于DFS序列[1,2,3,4]：

• 计算得dp[0][3] = 4，对应4种合法树结构：
  1. 1→2→3→4
  2. 1→2→3，1→2→4
  3. 1→2，1→3→4
  4. 1→2，1→3，1→4

内容的提问来源于stack exchange，提问作者Nguyễn Tùng Dương