Deep Dive into Dynamic Programming and Directed Acyclic Graphs: Algorithm Design Driven by Topological Sequences

Core Logic and Mathematical Principles

Directed Acyclic Graphs (DAGs) serve as a natural topological framework for Dynamic Programming (DP). Any DP problem that involves state transition equations can essentially be abstracted as a DAG, provided that there are no cyclic dependencies between states.

Running dynamic programming on a DAG (commonly referred to as Topological Sequence Driven DAG-DP) hinges on a core algebraic principle: the one-dimensional linear sequence of topological sorting strictly adheres to the "no aftereffect" constraint required by dynamic programming.

1. Topological Order Ensures Familiarization of State Space

Let the computation of state $v$ depend on predecessor states $u_1, u_2, ext{...}, u_k$. In the DAG topological graph, this is represented by the existence of directed edges $(u_i, v)$.

No Aftereffect Control: If we compute each node's corresponding DP state in ascending order according to the graph's topological order, then when the algorithm reaches node $v$, all predecessor nodes $u_i$ that can reach $v$ must have been fully dequeued and completed their decisions.
Mathematical Essence: Topological sorting flattens a branched structure into a linear progression chain. This ensures that when calculating the current state, the predecessor states are already in a familiarized state with a "deterministic algebraic solution", and any subsequent decisions cannot retroactively affect nodes that have already been computed.

2. Two Topological Trigger Tactics for State Transition

In practical coding implementations, there are two classic topological-driven tactics for DAG-DP:

Strategy A: Push-based (Contribution Method)
When a node $u$'s DP state is familiarized and ready to be dequeued, it proactively updates, accumulates, or relaxes the states of its successor nodes $v$ through all outgoing edges $(u, v)$. This method is particularly suitable for path counting and scheme accumulation (e.g., the longest food chain problem).
Strategy B: Pull-based (Memoization Search)
Starting from the final target or certain source points, it recursively requests the values of predecessor states in the reverse direction along the directed edges (inverse topological order) using DFS. A memo array is employed to intercept repeated recursion, and the underlying backtracking of this recursion strictly mirrors the inverse topological order.

Algorithm Derivation and State Design

Taking the classic problem of longest path and scheme count statistics in a directed acyclic graph as an example for state design.

1. State Definition

$dp[i]$: The longest path length from any valid topological starting point to node $i$.
$cnt[i]$: The optimal scheme count for reaching node $i$ with a path length exactly equal to $dp[i]$ from any valid topological starting point.

2. Topological Incremental State Transition Equation (Contribution Method)

When a zero in-degree node $u$ is dequeued from the topological queue, its states $dp[u]$ and $cnt[u]$ are fully familiarized. Traverse each outgoing edge $(u, v)$ starting from $u$, with edge weight $w$:

Longest Path Relaxation (Discovering a Better Topological Path):
If $dp[u] + w > dp[v]$, it indicates that passing through $u$ can provide a longer path to $v$.

$$dp[v] = dp[u] + w$$

$$cnt[v] = cnt[u] \\ ( ext{the scheme count is entirely inherited from } u)$$

Scheme Count Accumulation (Discovering Parallel Optimal Topological Paths):
If $dp[u] + w == dp[v]$, it indicates that another optimal path to $v$ of the same length has been found.

$$cnt[v] = (cnt[v] + cnt[u]) \\ ext{mod } MOD$$

C++ Standard Source Code (Topological Sequence Driven DAG-DP Standard Template)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

const int MAXN = 100005;
const long long MOD = 1000000007LL;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;

struct Edge {
    int to;
    long long weight;
};

std::vector<Edge> adj[MAXN];
int in_degree[MAXN];
int out_degree[MAXN];

long long dp[MAXN];  // dp[i] represents the longest path to node i
long long cnt[MAXN]; // cnt[i] represents the number of schemes to reach node i under the longest path condition

void dag_dp(int n) {
    std::queue<int> q;

    // 1. Initialize physical boundaries: Treat all nodes with an in-degree of 0 (topological sources) as the base for DP
    for (int i = 1; i <= n; ++i) {
        if (in_degree[i] == 0) {
            q.push(i);
            dp[i] = 0;   // Initial longest path for the starting point is 0
            cnt[i] = 1;  // Initial scheme count for the starting point is 1
        } else {
            dp[i] = -INF; // Other dangling points are initialized to negative infinity to prevent illegal transitions
            cnt[i] = 0;
        }
    }

    // 2. Topology-driven execution of DP transitions
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        // Traverse all outgoing edges from u to update subsequent node v (Push-based/Contribution method)
        for (size_t i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i].to;
            long long w = adj[u][i].weight;

            // Filter out invalid nodes with un-familiarized state (if the starting point is unreachable, skip relaxation)
            if (dp[u] == -INF) continue; 

            // Branch A: Discover a longer path, reset dp and scheme count
            if (dp[u] + w > dp[v]) {
                dp[v] = dp[u] + w;
                cnt[v] = cnt[u];
            }
            // Branch B: Discover a parallel optimal path, accumulate scheme count
            else if (dp[u] + w == dp[v]) {
                cnt[v] = (cnt[v] + cnt[u]) % MOD;
            }

            // Maintain the topological queue
            in_degree[v]--;
            if (in_degree[v] == 0) {
                q.push(v);
            }
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m;
    if (!(std::cin >> n >> m)) return 0;

    for (int i = 0; i < m; ++i) {
        int u, v;
        long long w;
        std::cin >> u >> v >> w;
        adj[u].push_back(Edge{v, w});
        in_degree[v]++;
        out_degree[u]++;
    }

    dag_dp(n);

    // 3. Global extreme value summary
    // Count the optimal states of all "sink nodes with out-degree 0"
    long long max_path_len = -INF;
    for (int i = 1; i <= n; ++i) {
        if (out_degree[i] == 0) {
            max_path_len = std::max(max_path_len, dp[i]);
        }
    }

    long long total_schemes = 0;
    for (int i = 1; i <= n; ++i) {
        if (out_degree[i] == 0 && dp[i] == max_path_len) {
            total_schemes = (total_schemes + cnt[i]) % MOD;
        }
    }

    if (max_path_len < 0) {
        std::cout << "No valid path\n";
    } else {
        std::cout << max_path_len << " " << total_schemes << "\n";
    }

    return 0;
}

NOIP Practical Pitfall Guide

Failure to Distinguish "Topological Sources of the Graph" from "Logically Specified Starting Points in the Problem":
If the problem explicitly specifies that the path must start from a certain fixed point $S$ during runtime, many contestants tend to initialize all nodes with in_degree == 0 as dp = 0, cnt = 1. This can lead to the inclusion of other zero in-degree sources that should not be counted, resulting in an inflated count of schemes and path lengths compared to the actual values.

Tactical Correction: If the problem specifies the starting point $S$, then only $dp[S] = 0, cnt[S] = 1$ should be set, while all other nodes, including those with an in-degree of 0, must be forcibly set to dp = -INF, cnt = 0.

Failure to Intercept Invalid Abandoned Nodes with -INF During State Transition:
As mentioned, if other zero in-degree points that are not the specified starting point remain as -INF, when they are dequeued, if the code does not include the condition if (dp[u] == -INF) continue;, directly executing dp[u] + w may cause negative overflow and erroneously relax and pollute the valid states of other nodes.

Classic NOIP/Luogu Problems

1. Luogu P1137 Travel Plan

Problem Description:
Xiaoming wants to travel to $N$ cities, and there are a total of $M$ directed roads between the cities. Due to the long distances, routes can only go from lower-numbered cities to higher-numbered cities (naturally ensuring it is a directed acyclic graph). Xiaoming wants to know how many cities can be included in the travel route that ends at each city.
Core Idea and Essence of the Problem:
Standard single-source/multi-source longest path DP in directed acyclic graphs.
Define $dp[i]$ as the longest path to city $i$ (including the number of cities). Since the path itself has no negative weights and all zero in-degree points are valid starting points, initialize all points with in_degree[i] == 0 as $dp[i] = 1$. Run the standard Kahn's topological sorting, and when node $u$ is dequeued, traverse the outgoing edges $(u, v)$ and execute the state transition equation: $dp[v] = ext{max}(dp[v], dp[u] + 1)$. Since the topological order of the graph guarantees the stability of stages, when the topological queue is empty, directly output $dp[1 ext{...} n]$ as the optimal solution for each point.

2. Luogu P1954 [NOI2010] Air Traffic Control

Problem Description:
There are $N$ planes that need to take off, and the takeoff must satisfy $M$ prerequisite relationships (such as plane $A$ must take off before plane $B$). Additionally, each plane has a latest takeoff position limit $k_i$, indicating that this plane must take off within the first $k_i$ positions. The requirements are: 1. Find a globally valid takeoff sequence. 2. Under all constraints, find the earliest takeoff position that each plane can strive for.
Core Idea and Essence of the Problem:
This is a comprehensive application problem that combines reverse topological sorting and greedy decision-making (DAG transformation).
It is difficult to arrange positions from front to back because the decisions made currently can severely constrain future limitations.
Reverse Topological Tactical Reconstruction: Consider the timeline in reverse to find the earliest takeoff position, which is equivalent to finding the latest takeoff position for that plane on the reverse graph.

Step One: Build the reverse graph, changing the original $A \to B$ to $B \to A$. Transform the plane's latest takeoff limits into constraints on the reverse graph.
Step Two: Use a max heap (priority queue) to maintain the currently zero in-degree planes. Each time a plane takes off, we greedily choose the one with the largest latest takeoff limit $k_i$ to place at the end of the reverse sequence. This way, more "tolerance" can be reserved for those planes with stricter constraints later.
Step Three (Finding the Earliest Position for Plane $X$): To allow $X$ to be as forward as possible in the reverse topology, we need to keep it as far back as possible. We can directly avoid letting $X$ enter the takeoff queue during the reverse topological iteration until the queue is empty and the algorithm can no longer proceed without scheduling $X$. At this point, the freed reverse position is essentially the earliest time that $X$ can be blocked in the reverse graph. After integer translation, this will correspond to the earliest takeoff position in the original graph. This entire solution perfectly suppresses the topological dependencies of the DAG.